Paul doesn’t like numbers with even length (we define the length of a number as the number of digits of the number), but he is wondering if he can create the odd length factorial sequence (OLFS). This sequence works in the following way: given a positive integer N, the $OLFS$ of N is the length of the $Nth$ factorial with odd length.

These are the first 10 OLFS:

N 0 1 2 3 4 5 6 7 8 9

OLFS 1 1 1 1 3 3 5 7 9 11

Explanation: for the numbers 0, 1, 2, 3, 5, 6, 8, 10, 12, 14 we have their respective factorials 1, 1, 2, 6, 120, 720, 40320, 3628800, 479001600, 87178291200.

Can you help our friend Paul to solve this task?

Input

The first line contains T($1 \leq T \leq 1000000$) the number of test cases. The next T lines contains an integer N ($0 \leq N \leq 3000066$), for which you should provide value of $OLFS(N)$.

Output

In the next T lines, print the calculated value $OLFS(N)$.