Power Substring

题意翻译

给你一个长为 $n$ 的正整数序列。 对于每个 $a_{i}$,你需要找到一个正整数 $k_{i}$ ,使得 $a_{i}$(十进制)是 $2^{k_{i}}$(十进制)最后 $\min(100$,$2^{k_{i}})$ 位的数字的一个子串。 不需要最小化 $k_{i}$。 问题中的十进制不包含前导零。 $1\le n\le 2000$,$1\le a_i\le 10^{11}$,正整数 $k_{i}$ 必须满足 $1\le k_i\le 10^{50}$。 保证有解。 如果有多个答案,输出任意一个。

题目描述

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<=2000 $ ) — the number of integers $ a_{i} $ . Each of the next $ n $ lines contains a positive integer $ a_{i} $ ( $ 1<=a_{i}<10^{11} $ ).

输出格式


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^{50} $ . It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

2
8
2

输出样例 #1

3
1

输入样例 #2

2
3
4857

输出样例 #2

5
20