Source

The problem is proposed by . All rights reserved.

Problem source: http://8.136.99.126/blog/114/686bb169ab85cef1c18668cc

Problem Description

Construct a binary string $S$ of length $n$ containing exactly $m$ subsequences $\texttt{01}$, or determine that no solution exists.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$ indicating the number of test cases.

Each of the next $T$ lines contains two non-negative integers $n$ and $m$.

Output Format

If a solution exists, output the constructed 01 string. Otherwise, output $n$ exclamation marks (!, ASCII code $33$).

Samples

4
2 4
6 8
10 12
14 16

!!
001111
0101011100
11100001111000

Tips

For $50\%$ of the test cases, $n \le 100$ and $m \le 10^4$.

For $100\%$ of the test cases, $1 \le T \le 10^4$, $1 \le n \le 10^6$, and $0 \le m \le 10^{18}$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^6$.