쓰레기통

여러분이 사는 도시 Kickstartland에는 $\mathbf{N}$채의 집이 있는 유난히 긴 거리 하나가 있다. 이 거리의 길이는 $\mathbf{N}$이며, $\mathbf{N}$채의 집은 거리를 따라 균등하게 배치되어 있다. 즉, 첫 번째 집은 위치 $1$에, 두 번째 집은 위치 $2$에 있으며, 이런 식으로 이어진다. 임의의 두 집 $i$와 $j$ 사이의 거리는 $|i-j|$이며, 여기서 $|x|$는 $x$의 절댓값을 나타낸다.

이 집들 중 일부는 집 앞에 쓰레기통이 있다. 이는 그런 집의 주인들은 쓰레기를 버리려고 할 때 걸을 필요가 없다는 뜻이다. 하지만 집 앞에 쓰레기통이 없는 집의 주인들은 자신의 집에서 왼쪽이나 오른쪽 방향에 있는, 집 앞에 쓰레기통이 있는 어떤 집까지 걸어가야 한다.

시간을 절약하기 위해 모든 집주인은 항상 자신의 집에서 가장 가까운 쓰레기통에 쓰레기를 버린다. 어떤 집에서 가장 가까운 쓰레기통이 두 개라면, 그 집주인은 그중 어느 곳으로든 걸어갈 수 있다.

집의 수 $\mathbf{N}$와 이 집들 중 어느 집 앞에 쓰레기통이 있는지에 대한 설명이 주어질 때, 각 집주인이 쓰레기를 버리기 위해 걸어야 하는 거리의 합을 구한다. 적어도 한 집 앞에는 쓰레기통이 있다고 가정해도 된다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 길이는 $\mathbf{N}$와 같다. $\mathbf{S}$의 각 문자는 $0$ 또는 $1$이다. $\mathbf{S}$에는 문자 $1$이 적어도 하나 있다.

테스트 세트 1

$1 \le \mathbf{N} \le 100$.

테스트 세트 2

$1 \le \mathbf{N} \le 5 \times 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫 번째 줄에는 거리에 있는 집의 수를 나타내는 정수 $\mathbf{N}$이 주어진다.

각 테스트 케이스의 두 번째 줄에는 어느 집 앞에 쓰레기통이 있는지를 나타내는 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다. 문자열 $\mathbf{S}$의 $i$번째 문자가 $1$과 같다면, 이는 $i$번째 집 앞에 쓰레기통이 있다는 뜻이다. 그렇지 않고 그 문자가 $0$와 같다면, 이는 $i$번째 집 앞에 쓰레기통이 없다는 뜻이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호이며(1부터 시작한다), $y$은 각 집주인이 쓰레기를 버리기 위해 걸어야 하는 거리의 합이다.

첫 번째 테스트 케이스에서는 모든 집 앞에 쓰레기통이 있으므로 어떤 집주인도 쓰레기를 버리기 위해 걸을 필요가 없다.

두 번째 테스트 케이스에서는 첫 번째 집과 네 번째 집의 주인 집 앞에 쓰레기통이 있으므로 이들은 걸을 필요가 없다. 두 번째 집의 주인은 첫 번째 집을 향해 걸으며, 거리는 $1$와 같다. 세 번째, 다섯 번째, 여섯 번째 집의 주인은 네 번째 집을 향해 걸으며, 거리는 각각 $1$, $1$, $2$와 같다.