Smallest K

Time limit1sMemory limit128 MB

Summary
Find, for each given R, the smallest exponent k such that the last R decimal digits of 2^k are all 1s or 2s, using digit-by-digit lifting with modular arithmetic.
Level

Hard8 of 10

Topics
Number theory, Math, Brute force
Solved
No attempts yet

Problem

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:

RSmallest kLast R digits of 2^k
112
2912
389112
4892112
558922112
63089122112

Input

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)

Output

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

Examples1

  1. Example 1

    Input
    6
1
2
4
5
7
15
    Expected output
    1
9
89
589
3089
11687815589