muxusetre

"Viața e grea. Mai bine nu treci prin toate greutățile, dă-i skip!"

Mux a fost în parc și a găsit pe o bancă $t$ șiruri de $0$ și $1$. El are nevoie să afle câte secvențe bune conține șirul.
Denumim o secvență ca fiind bună, dacă diferența dintre numărul de $0$ și numărul de $1$ din secvență este pară. Observați că această diferență nu trebuie să fie neapărat pozitivă.

Cerință

Dându-se $t$ șiruri, spuneți pentru fiecare șir câte secvențe au diferența dintre numărul de $0$ și numărul de $1$ din secvență număr par.

Date de intrare

Pe prima linie este numărul $t$, iar apoi pe a $2 \cdot i$ și pe a $2 \cdot i + 1$-a linie $(1 \leq i \leq t)$ se va afla lungimea celui de-al $i$-lea șir găsit de Mux, respectiv șirul.

Date de ieșire

Pe a $i$-a linie $(1 \leq i \leq t)$ se va afla răspunsul la întrebarea lui Mux pentru cel de-al $i$-lea șir.

Restricții și precizări

• $1 \leq t \leq 1 \ 000$;
• $1 \leq n \leq 10^6$, unde $n$ este lungimea fiecărui șir
• Șirul conține doar caracterele $0$ și $1$.
• Suma lungimilor celor $t$ șiruri de caractere nu depășește $10^6$.
• Notă. Această problemă nu are nicio legătură cu problema suxumetre

Exemplu

stdin

4
9
010100100
7
0000000
18
100100010111010111
11
00000000000

stdout

20
12
81
30

Explicație

Pentru primul șir, câteva din subsecvențele ce respectă proprietatea cerută sunt 0101, 10, 1001 etc.