{"raw_statement":[{"iden":"statement","content":"A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its *decimal* representation with her calculator.\n\nUnfortunately, her calculator cannot work on any integer larger than $K$ and it will crash. Therefore, Ayu may need to remove zero or more bits from $S$ while maintaining the order of the remaining bits such that its decimal representation is no larger than $K$. The resulting binary string also must not contain any leading zeroes.\n\nYour task is to help Ayu to determine the minimum number of bits to be removed from $S$ to satisfy Ayu's need.\n\nFor example, let $S$ = _1100101_ and $K = 13$. Note that _1100101_ is $101$ in decimal representation, thus, we need to remove several bits from $S$ to make it no larger than $K$. We can remove the $3^(r d)$, $5^(t h)$, and $6^(t h)$ most significant bits, i.e. _1100101_ $arrow.r$ _1101_. The decimal representation of _1101_ is $13$, which is no larger than $K = 13$. In this example, we removed $3$ bits, and this is the minimum possible (If we remove only $2$ bits, then we will have a binary string of length $5$ bits; notice that any binary string of length $5$ bits has a value of at least $16$ in decimal representation).\n\nInput begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes.\n\nOutput contains an integer in a line representing the minimum number of bits to be removed from $S$.\n\n_Explanation for the sample input/output #1_\n\nThis sample is illustrated by the example given in the problem description above.\n\n_Explanation for the sample input/output #2_\n\nAyu must remove $4$ bits to get _111_, which is $7$ in its decimal representation.\n\n"},{"iden":"input","content":"Input begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes."},{"iden":"output","content":"Output contains an integer in a line representing the minimum number of bits to be removed from $S$."},{"iden":"examples","content":"Input13\n1100101\nOutput3\nInput13\n1111111\nOutput4\n"},{"iden":"note","content":"_Explanation for the sample input/output #1_This sample is illustrated by the example given in the problem description above._Explanation for the sample input/output #2_Ayu must remove $4$ bits to get _111_, which is $7$ in its decimal representation."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of days.  \n- Let $ V = (v_1, v_2, \\dots, v_n) $ be a sequence where $ v_i \\in \\{0\\} \\cup \\{1, 2, \\dots, n\\} $, with $ v_1 = 1 $ and at least one $ v_i = 0 $.  \n- A **valid sequence** $ D = (d_1, d_2, \\dots, d_n) $ satisfies:  \n  1. $ d_i = v_i $ for all $ v_i > 0 $.  \n  2. There exists a strictly increasing sequence of days $ 1 = d^{(1)} < d^{(2)} < \\dots < d^{(k)} \\leq n $ such that on day $ d^{(j)} $, Mr. Light learns meal $ j $ for the first time.  \n  3. For all days $ t \\in [d^{(j)}, d^{(j+1)} - 1] $, the meal cooked on day $ t $ is $ ((t - d^{(j)}) \\bmod j) + 1 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 4096 $  \n2. $ 2 \\leq n \\leq 10^5 $  \n3. $ v_1 = 1 $, $ v_i \\in [0, n] $, at least one $ v_i = 0 $  \n4. The sum of $ n $ over all test cases $ \\leq 6 \\times 10^6 $  \n5. At least one valid completion exists.  \n\n**Objective**  \nFor each test case, find the **minimum** $ k \\in \\mathbb{Z}^+ $ such that there exists a valid sequence $ D $ with exactly $ k $ distinct meals learned, and output:  \n- The value $ k $,  \n- A valid sequence $ D = (d_1, \\dots, d_n) $ satisfying all constraints.","simple_statement":"Mr. Light learns one new meal on day 1, and each time he learns a new meal, he starts cycling through all meals he knows in order, one per day. Some days' meals are missing (marked as 0). Find the minimum number of meals he could have learned, and fill in the missing days with valid meal numbers.","has_page_source":false}