← 返回题目列表

Codeforces · 913/G

G. 电源子串

中文机器翻译题面 查看原题

给定 n 个正整数 a1, a2, ..., an。

对于每个 ai,您需要找到一个正整数 ki,使得 2ki 的十进制表示法包含 ai 的十进制表示法作为其最后 min(100, length(2ki)) 数字中的子字符串。这里length(m)是m的十进制长度。

请注意,您不必最小化 ki。此问题中的小数表示法不包含前导零。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2 000) — 整数 ai 的数量。

接下来的 n 行中的每一行都包含一个正整数 ai (1 ≤ ai < 1011)。

输出

打印 n 行。其中第 i 个应包含正整数 ki,使得 2ki 的最后 min(100, length(2ki)) 数字包含 ai 作为子字符串的十进制表示法。整数 ki 必须满足 1 ≤ ki ≤ 1050。

可以证明,在给定的约束条件下,答案总是存在。如果有多个答案,请打印其中任何一个。

示例

输入 #1

2
8
2

输出 #1

3
1

输入 #2

2
3
4857

输出 #2

5
20