The Number Of Good Substrings

You are given a binary string s (recall that a string is binary if each character is either 0 or 1).

Let f(t) be the decimal representation of integer t written in binary form (possibly with leading zeroes). For example f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0 and f(000100) = 4.

The substring s_{l}, s_{l+1}, ... , s_{r} is good if r - l + 1 = f(s_l ... s_r).

For example string s = 1011 has 5 good substrings: s_1 ... s_1 = 1, s_3 ... s_3 = 1, s_4 ... s_4 = 1, s_1 ... s_2 = 10 and s_2 ... s_4 = 011.

Your task is to calculate the number of good substrings of string s.

You have to answer t independent queries.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of queries.

The only line of each query contains string s (1 ≤ |s| ≤ 2 ⋅ 10^5), consisting of only digits 0 and 1.

It is guaranteed that ∑_{i=1}^{t} |s_i| ≤ 2 ⋅ 10^5.

Output

For each query print one integer — the number of good substrings of string s.

Example

Input

4 0110 0101 00001000 0001000

Output

4 3 4 3

inputFormat

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of queries.

The only line of each query contains string s (1 ≤ |s| ≤ 2 ⋅ 10^5), consisting of only digits 0 and 1.

It is guaranteed that ∑_{i=1}^{t} |s_i| ≤ 2 ⋅ 10^5.

outputFormat

Output

For each query print one integer — the number of good substrings of string s.

Example

Input

4 0110 0101 00001000 0001000

Output

4 3 4 3

样例

4
0110
0101
00001000
0001000

4
3
4
3

</p>