CF2242E Product of Closures

Let the closure of a positive integer $ x \gt 0 $ be the following infinite binary string $ C(x) $ : 1. Write $ x $ in binary form without leading zeros; 2. Concatenate the obtained string with itself infinitely many times and call the result $ C(x) $ . For example, $ C(1) $ $ = $ 11111..., $ C(4) $ $ = $ 10010010010010..., $ C(9) $ $ = $ 100110011001.... Let the product of two closures $ C(x) \mathop{\&} C(y) $ be the infinite binary string obtained by the bitwise binary AND of the strings $ C(x) $ and $ C(y) $ . For example, for $ C(4) \mathop{\&} C(9) $ we get $$$ \begin{array}{r} \begin{array}{r} C(4)\\ C(9)\\ \end{array} \mathop{\&} \begin{array}{r} 100100100100100100...\\ 100110011001100110...\\ \end{array} \\ \hline \begin{array}{r} 100100000000100100... \end{array} \end{array} $$$ You are given three integers $ l $ , $ r $ , and $ n $ . Among all numbers in the segment $ [l, r] $ , find two integers $ x $ and $ y $ ( $ l \le x \lt y \le r $ ) such that $ C(x) \mathop{\&} C(y) $ is lexicographically smallest, and print the first $ n $ binary symbols of this product.

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The only line of each test case contains three integers $ l $ , $ r $ , and $ n $ ( $ 1 \le l \lt r \lt 2^{30} $ ; $ 1 \le n \le 1000 $ ) — the range of possible values and the length of the answer.

For each test case, print one binary string of length $ n $ — the first $ n $ symbols of the lexicographically smallest product of closures.

In the first test case, the lexicographically smallest string is obtained by the product $ C(2) \mathop{\&} C(4) $ .