{"problem":{"name":"G. Power Substring","description":{"content":"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_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF913G"},"statements":[{"statement_type":"Markdown","content":"You are given _n_ positive integers _a_1, _a_2, ..., _a__n_.\n\nFor 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_.\n\nNote that you don't have to minimize _k__i_. The decimal notations in this problem do not contain leading zeros.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 2 000) — the number of integers _a__i_.\n\nEach of the next _n_ lines contains a positive integer _a__i_ (1 ≤ _a__i_ < 1011).\n\n## Output\n\nPrint _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.\n\nIt can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]。\n\n对于每个 #cf_span[ai]，你需要找到一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的十进制表示在其最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。这里 #cf_span[length(m)] 表示 #cf_span[m] 的十进制表示的长度。\n\n注意，你无需最小化 #cf_span[ki]。本题中的十进制表示不包含前导零。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2 000]) —— 整数 #cf_span[ai] 的个数。\n\n接下来的 #cf_span[n] 行，每行包含一个正整数 #cf_span[ai] (#cf_span[1 ≤ ai < 1011])。\n\n请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。要求 #cf_span[ki] 满足 #cf_span[1 ≤ ki ≤ 1050]。\n\n可以证明，在给定约束下答案一定存在。如果存在多个答案，输出任意一个即可。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2 000]) —— 整数 #cf_span[ai] 的个数。接下来的 #cf_span[n] 行，每行包含一个正整数 #cf_span[ai] (#cf_span[1 ≤ ai < 1011])。\n\n## Output\n\n请输出 #cf_span[n] 行。第 #cf_span[i] 行应包含一个正整数 #cf_span[ki]，使得 #cf_span[2ki] 的最后 #cf_span[min(100, length(2ki))] 位中包含 #cf_span[ai] 的十进制表示作为子串。要求 #cf_span[ki] 满足 #cf_span[1 ≤ ki ≤ 1050]。可以证明，在给定约束下答案一定存在。如果存在多个答案，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 2000 $.  \nGiven $ a_1, a_2, \\dots, a_n \\in \\mathbb{N} $, with $ 1 \\leq a_i < 10^{11} $ for all $ i \\in \\{1, 2, \\dots, n\\} $.\n\nFor each $ a_i $, find $ k_i \\in \\mathbb{N} $, $ 1 \\leq k_i \\leq 10^{50} $, such that the decimal representation of $ 2^{k_i} $, when restricted to its last $ \\min(100, \\lfloor \\log_{10}(2^{k_i}) \\rfloor + 1) $ digits, contains the decimal representation of $ a_i $ as a contiguous substring.\n\nThat is, let $ d(m) $ denote the decimal representation of a positive integer $ m $ (without leading zeros).  \nLet $ L_i = \\min\\left(100, \\left\\lfloor \\log_{10}(2^{k_i}) \\right\\rfloor + 1\\right) $.  \nThen, $ d(a_i) $ must be a substring of the suffix of $ d(2^{k_i}) $ of length $ L_i $.\n\nOutput $ k_1, k_2, \\dots, k_n $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF913G","tags":["math","number theory"],"sample_group":[["2\n8\n2","3\n1"],["2\n3\n4857","5\n20"]],"created_at":"2026-03-03 11:00:39"}}