题目描述

江桥需要一个只包含字符 0 和 1 的字符串，使得这个字符串的所有全 1 子串的数量恰好为 $k$。

例如， 01100 有三个全 1 子串 1,11,1。其中第一个 1 是原字符串中的第 $2$ 个字符组成的子串，第二个 1 是原字符串中的第 $3$ 个字符组成的子串。这两个子串被视为不同。

江桥希望你构造一个最短的字符串满足条件，同时如果最短的有多个， 他希望你能输出一个字典序最小的字符串。 七萤赶忙制止了江桥，并说只需要输出任意一个满足条件的最短的字符串即可。

输入格式

第一行一个正整数 $T$，表示 $T$ 组询问。

对于每组询问，一行一个正整数 $k$，表示字符串的全 1 子串的数量。

输出格式

容易证明，一定存在至少一个满足条件的字符串，输出任意一个最短的满足条件的字符串。

5
3
10
15
16
16

11
1111
11111
1011111
1111101

5
20
9
12
10
13

111101111
110111
1110111
1111
1101111

样例解释

无

数据规模与约定

下发文件

下发文件对应子任务 $1$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 200,1 \leq k \leq 2 \times 10^{5}$。