You are given n positive integers a₁, a₂, ..., 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¹¹).

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

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

Power Substring

Examples