版权声明

本题版权归 所有。

题目来源：http://8.136.99.126/blog/114/686bb169ab85cef1c18668cc

题目描述

试构造一个长度为 $n$ 的 01 串 $S$，使得其中恰好有 $m$ 个子序列 $\texttt{01}$，或报告无解。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

下面 $T$ 行，每行两个非负整数 $n,m$。

输出格式

如果有解，输出构造出的 01 串，否则输出 $n$ 个半角感叹号（!，ASCII 码为 $33$）。

样例

4
2 4
6 8
10 12
14 16

!!
001111
0101011100
11100001111000

提示

对于 $50\%$ 的数据，$n \le 100$，$m \le 10^4$。

对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^6$，$0 \le m \le 10^{18}$。

保证所有数据中 $n$ 的和不大于 $10^6$。