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.

设正整数 $x > 0$ 的闭包（closure）为如下无限二进制字符串 $C(x)$：

1. 将 $x$ 写成不含前导零的二进制形式；
2. 将所得字符串无限次地自我拼接，结果即为 $C(x)$。

例如：$C(1) = 11111\ldots$，$C(4) = 10010010010010\ldots$，$C(9) = 100110011001\ldots$。

定义两个闭包 $C(x)$ 与 $C(y)$ 的乘积 $C(x) \mathop{\&} C(y)$ 为对无限二进制字符串 $C(x)$ 和 $C(y)$ 逐位执行二进制按位与（bitwise AND）运算所得的无限二进制字符串。例如，对 $C(4) \mathop{\&} C(9)$，我们得到：

$$\begin{array}{r} \begin{array}{r} C(4)\\ C(9)\\ \end{array} \mathop{\&} \begin{array}{r} 100100100100100100\ldots\\ 100110011001100110\ldots\\ \end{array} \\ \hline \begin{array}{r} 100100000000100100\ldots \end{array} \end{array}$$

给定三个整数 $l$、$r$ 和 $n$。在区间 $[l, r]$ 中的所有整数中，找出两个整数 $x$ 和 $y$（满足 $l \le x < y \le r$），使得 $C(x) \mathop{\&} C(y)$ 的字典序最小，并输出该乘积的前 $n$ 个二进制符号。

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.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例仅有一行，包含三个整数 $l$、$r$ 和 $n$（$1 \le l \lt r \lt 2^{30}$；$1 \le n \le 1000$）—— 可能取值的范围以及答案的长度。

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

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串——字典序最小的闭包乘积的前 $n$ 个符号。

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

在第一个测试用例中，字典序最小的字符串由乘积 $C(2) \mathop{\&} C(4)$ 得到。