You are given $*n*$ positive integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$.

For every $*a*_{*i*}$ you need to find a positive integer $*k*_{*i*}$ such that the decimal notation of $2^{*k*_{*i*}}$ contains the decimal notation of $*a*_{*i*}$ as a substring among its last $*min*(100, *length*(2^{*k*_{*i*}}))$ digits. Here $*length*(*m*)$ is the length of the decimal notation of $*m*$.

Note that you don't have to minimize $*k*_{*i*}$. The decimal notations in this problem do not contain leading zeros.

Input

The first line contains a single integer $*n*$ ($1 ≤ *n* ≤ 2 000$) — the number of integers $*a*_{*i*}$.

Each of the next $*n*$ lines contains a positive integer $*a*_{*i*}$ ($1 ≤ *a*_{*i*} < 10^{11}$).

Output

Print $*n*$ lines. The $*i*$-th of them should contain a positive integer $*k*_{*i*}$ such that the last $*min*(100, *length*(2^{*k*_{*i*}}))$ digits of $2^{*k*_{*i*}}$ contain the decimal notation of $*a*_{*i*}$ as a substring. Integers $*k*_{*i*}$ must satisfy $1 ≤ *k*_{*i*} ≤ 10^{50}$.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.