对于一个正整数 $x$，先写出 $x$ 的二进制表示，并去掉所有前导零。设得到的二进制字符串为 $s$。

定义 $x$ 的闭包 $C(x)$ 为将字符串 $s$ 无限重复得到的无限二进制串。

例如：

• $C(1)=111111\ldots$；
• $C(4)=100100100100\ldots$；
• $C(9)=100110011001\ldots$。

对于两个正整数 $x$ 和 $y$，定义 $C(x)\mathbin{\&}C(y)$ 为两个无限二进制串逐位进行按位与运算后得到的无限二进制串。

例如，$C(4)=100100100100\ldots$，$C(9)=100110011001\ldots$，因此

$$C(4)\mathbin{\&}C(9)=100100000000100100\ldots$$

现在给定三个整数 $l,r,n$。

你需要从区间 $[l,r]$ 中选择两个不同的整数 $x,y$，满足

$$l\le x<y\le r,$$

并使无限二进制串 $C(x)\mathbin{\&}C(y)$ 的字典序尽可能小。

对于两个不同的无限二进制串，从左向右找到第一个不同的位置，该位置上字符为 0 的串字典序更小。

请输出能够得到的字典序最小的无限二进制串的前 $n$ 个字符。

注意，取得最优值的整数对 $(x,y)$ 可能不唯一，但需要输出的最小二进制串是唯一确定的。

输入

第一行包含一个整数 $t$（$1\le t\le1000$），表示测试数据组数。

接下来 $t$ 行，每行包含三个整数 $l,r,n$（$1\le l<r<2^{30}$，$1\le n\le1000$）。

其中 $[l,r]$ 表示可以选择整数的范围，$n$ 表示需要输出的二进制字符数量。

输出

对于每组测试数据，输出一个长度恰好为 $n$ 的二进制字符串，表示所有合法整数对 $(x,y)$ 中，字典序最小的 $C(x)\mathbin{\&}C(y)$ 的前 $n$ 个字符。

样例

Input1

3
2 5 12
5 6 15
17 40 20

Output1

100000100000
100100100100100
10000000000000000000

说明

对于第一组测试数据，可以选择 $x=2,y=4$。

$2$ 的二进制表示为 10，因此 $C(2)=101010\ldots$；$4$ 的二进制表示为 100，因此 $C(4)=100100\ldots$。

逐位进行按位与后得到

$$C(2)\mathbin{\&}C(4)=100000100000\ldots$$

可以证明，不存在其他合法整数对能够得到字典序更小的无限二进制串，因此输出其前 $12$ 个字符。

数据范围

对于所有测试数据，满足：

$$1\le t\le1000,$$

$$1\le l<r<2^{30},$$

$$1\le n\le1000.$$

定义以下特殊性质：

• 性质 A：对于所有测试数据，均有 $n=1$；
• 性质 B：对于所有测试数据，均有 $r=l+1$；
• 性质 C：对于每组测试数据，都存在正整数 $k$，使得 $l<2^k\le r$；
• 性质 D：对于每组测试数据，$l$ 与 $r$ 的二进制表示长度相同。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点编号	$t$	$r$	$n$	特殊性质
$1$	$\le5$	$<2^5$	$\le20$	无
$2$	$\le10$	$<2^8$	$\le50$
$3\sim4$	$\le20$	$<2^{12}$	$\le100$
$5\sim6$	$\le100$	$<2^{20}$	$\le200$
$7$	$\le1000$	$<2^{30}$	$1$	A
$8$			$\le1000$	B
$9$				C
$10$				D
$11\sim12$	$\le200$	$<2^{25}$	$\le500$	无
$13\sim14$	$\le500$	$<2^{30}$	$\le1000$
$15\sim20$	$\le1000$