F-小红的01串（hard）_牛客周赛 Round 102

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的困难版本，两题的区别在于 $T$ 的数据范围不同，且本题需要输出任意一个符合要求的 01 串。

$\hspace{15pt}$ 小红定义一个仅由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串（简称 01 串）的权值为：
$\hspace{23pt}\bullet\,$ 仅由 $\texttt{`1'}$ 构成的连续子串的数量。
$\hspace{15pt}$ 现给定正整数 $k$ ，请找到最短的权值为 $k$ 的 01 串，输出任意一个符合要求的答案。

【名词解释】
$\hspace{15pt}$ 连续子串：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 。

输出描述:

对于每一组测试数据，新起一行，输出一个 01 串代表答案。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

2
3
20

输出

复制

11
111101111