A sequence of coin toss can be encoded as a binary string, ’0’ for head, ’1’ for tail. Given an encoded sequence \(S\),
toss the coin until \(S\) appears in the result sequence then stop.
Let \(T\) be the number of coin toss taken for \(S\) to appear, find the expected value of \(T\).

Input

The first line of input contains the one integer \(Q\) (\(1 \leq Q \leq 10^4\)), the number of test cases. The following \(Q\) lines, each contains a string \(S\) (\(1 \leq |S| \leq 20\))

Output

Output \(Q\) lines, each contains the respective value of \(T\). The answer is considered correct if the precision error is less than \(10^{-9}\)

Example

1
00

6