狐狸肉松是一位精通各种字符串处理的字符串大师。例如，他可以用舌头编织面条。同样，他在计算机编程中的字符串数据类型方面也非常擅长。

一天晚上，肉松做了一个梦，梦见他在吃面条时从碗里挑出了一条无限长的字符串。仔细观察后，发现这是一个仅包含零和一的二进制字符串，由 $0, 1, 10, 11, \dots$ 连接而成。形式化地，定义字符串 $s^0 = 0$，对于每个整数 $i > 0$，定义 $s^i = s^{i-1} + (i)_2$，其中 $a + b$ 表示字符串 $a$ 和 $b$ 的连接，$(i)_2$ 表示整数 $i$ 的二进制形式（不含前导零）。因此，肉松梦见的无限长字符串为 $s^\infty = 011011100101 \dots$。

由于 $s^\infty$ 的长度太大，肉松只想关注从第 $l$ 个字符到第 $r$ 个字符的子串，记为 $s^\infty_{l,r}$。他想在字符串 $s^\infty_{l,r}$ 中找到长度为 $n$ 且字典序最大的子串。形式化地，请找到一个索引 $i$，满足 $l \le i \le r - n + 1$，使得 $s^\infty_{i,i+n-1}$ 的字典序最大。你能在他醒来之前帮肉松解决这个问题吗？

对于两个长度相同的二进制字符串 $a$ 和 $b$，如果它们在第一个不同的位置 $i$ 上，$a$ 的第 $i$ 个字符为 $1$ 而 $b$ 的第 $i$ 个字符为 $0$，则称字符串 $a$ 的字典序大于字符串 $b$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例包含三个整数 $l, r, n$ ($1 \le l \le r \le 10^{18}$, $1 \le n \le \min(r - l + 1, 10^6)$)，表示关注的范围和子串的长度。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出字典序最大的子串，每个结果占一行。

样例

输入 1

6
6 13 3
1 9 9
1 1451419198 10
987 6543 21
1123 581321 34
1000010 1000030 18

输出 1

110
011011100
1111111111
111111111100000000010
1111111111111111000000000000000100
000111110011010000

说明

对于样例中的第一个测试用例，$s^\infty = 011011100101110111 \dots$，因此 $s^\infty_{6,13} = 11001011$。长度为 $3$ 的子串有 $110, 100, 001, 010, 101, 011$。其中字典序最大的是 $110$。