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 < 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.