Power Substring
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.
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*<=&lt;<=1011).
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*<=≤<=1050.

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