给定 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