让 关闭 正整数 $$$x \gt 0$$$ 的 是以下无限二进制字符串 $$$C(x)$$$:
- 以二进制形式写入$$$x$$$,不带前导零;
- 将获得的字符串与其自身连接无限次,并将结果调用$$$C(x)$$$。
例如,$$$C(1)$$$ $$$=$$$ 11111...,$$$C(4)$$$$$$=$$$ 10010010010010...,$$$C(9)$$$$$$=$$$ 100110011001....
让 产品 两个闭包的 $$$C(x) \mathop{\&} C(y)$$$ 是通过以下方式获得的无限二进制字符串 按位 二进制 和 字符串 $$$C(x)$$$ 和 $$$C(y)$$$ 的 。例如,对于 $$$C(4) \mathop{\&} C(9)$$$ 我们得到
$$\begin{array}{r} \begin{array}{r} C(4)\\ C(9)\\ \end{array} \mathop{\&} \begin{array}{r} 100100100100100100...\\ 100110011001100110...\\ \end{array} \\ \hline \begin{数组}{r} 100100000000100100... \end{数组} \end{数组}$$
给你三个整数 $$$l$$$、$$$r$$$ 和 $$$n$$$。在 $$$[l, r]$$$ 段中的所有数字中,找到两个整数 $$$x$$$ 和 $$$y$$$ ($$$l \le x \lt y \le r$$$) 使得 $$$C(x) \mathop{\&} C(y)$$$ 为 字典顺序最小,并打印该乘积的前 $$$n$$$ 二进制符号。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的唯一行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$n$$$ ($$$1 \le l \lt r \lt 2^{30}$$$; $$$1 \le n \le 1000$$$) — 可能值的范围和答案的长度。
输出
对于每个测试用例,打印一个长度为 $$$n$$$ 的二进制字符串 — 按字典顺序排列的最小闭包乘积的第一个 $$$n$$$ 符号。
示例
输入复制
31 4 101073741822 1073741823 3510 20 15
输出复制
100000100011111111111111111111111111111011111100000000010000
注意
在第一个测试用例中,字典顺序最小的字符串是通过乘积 $$$C(2) \mathop{\&} C(4)$$$ 获得的。