Given an nonnegative integer x, Chiaki can perform the following two operations:

• obtain x-1 from x.
• x-2ⁱ from x, if is not 0.

Let f(x, y) be the minimum operations needed to change x to y using the above operations, Chiaki would like to know the value of where n is a given number.

输入描述:

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n in binary representation (0 ≤ n < 2500) without leading zeros.
It's guaranteed that the sum of lengths of n over all test cases will not exceed 500.

输出描述:

For each test case, output the answer modulo (109+7).

10
0
1
10
11
100
101
110
111
1000
1001

0
1
3
7
13
22
31
43
60
83