Smallest K

You are given an integer R. Find the smallest positive integer k such that the last R decimal digits of 2^k are all either 1 or 2.

For illustration, 2^9 = 512, so k = 9 works when R = 2. The last four digits of 2^89 are 2112, so k = 89 works for both R = 3 and R = 4.

The answers up to R = 6 are:

The first line contains the number of test cases T. (1 ≤ T ≤ 50)

Each of the next T lines contains one integer R. (1 ≤ R ≤ 20)

For each test case, print the smallest k satisfying the condition on its own line.