对于任意二进制字符串 $$$t$$$$$$^{\text{∗}}$$$,设 $$$f(t)$$$ 为 $$$t$$$ 中仅包含 $$$\mathtt{0}$$$ 的非空子序列 $$$^{\text{†}}$$$ 的数量,并设 $$$g(t)$$$ 为$$$t$$$ 的非空子序列,其中至少包含一个 $$$\mathtt{1}$$$。
请注意,对于 $$$f(t)$$$ 和 $$$g(t)$$$,每个子序列的计数次数与它在 $$$t$$$ 中出现的次数相同。例如,$$$f(\mathtt{000}) = 7,g(\mathtt{100}) = 4$$$。
我们将二进制字符串$$$t$$$的唯一性定义为$$$|f(t)-g(t)|$$$,其中对于任意整数$$$z$$$,$$$|z|$$$表示$$$z$$$的绝对值。
给你一个正整数$$$n$$$。找到一个长度为$$$n$$$的二进制字符串$$$s$$$,使其单一性尽可能小。如果有多个字符串,则可以打印其中任何一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — $$$s$$$ 的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,在新行中输出 $$$s$$$。如果存在多个答案,则输出任何一个。
示例
输入 #1
3 1 2 3
输出 #1
0 01 010
注意
在第一个测试用例中,对于示例输出,$$$f(t)=1$$$ 因为有一个子序列仅包含 $$$\mathtt{0}$$$ ($$$\mathtt{0}$$$),并且 $$$g(t)=0$$$ 因为不存在至少包含一个 $$$1$$$ 的子序列。唯一性是$$$|1-0|=1$$$。输出 $$$\mathtt{1}$$$ 也是正确的,因为它的唯一性是 $$$|0-1|=1$$$。
对于第二个测试用例的示例输出,$$$f(t)=1$$$ 因为有一个非空子序列仅包含 $$$\mathtt{0}$$$,而 $$$g(t)=2$$$ 因为有两个非空子序列至少包含一个 $$$\mathtt{1}$$$ ($$$\mathtt{01}$$$ 和 $$$\mathtt{1}$$$)。因此,单一性是$$$|1-2|=1$$$。可以证明,$$$1$$$ 是所有大小为$$$2$$$ 的可能二进制字符串中唯一性的最小可能值。