Let the closure of a positive integer $$$x \gt 0$$$ be the following infinite binary string $$$C(x)$$$:

Write $$$x$$$ in binary form without leading zeros;
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.

Input

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.

Output

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

Note

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

Product of Closures

Examples