回想一下 $n$ 个元素的中位数的定义（其中 $n$ 为奇数）：将这些元素排序，中位数即为第 $\frac{n+1}{2}$ 大的元素。

在本题中，每个元素的具体数值并未给出，但给出了其中一些元素对之间的 $m$ 个关系。第 $i$ 个关系可以描述为 $(a_i, b_i)$，表示第 $a_i$ 个元素严格大于第 $b_i$ 个元素。

对于所有的 $1 \le k \le n$，是否可能为每个元素赋值，使得所有关系都得到满足，且第 $k$ 个元素是这 $n$ 个元素的中位数？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n < 100, 1 \le m \le n^2$)，分别表示元素的个数和关系的个数。保证 $n$ 为奇数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $a_i$ 个元素严格大于第 $b_i$ 个元素。保证对于所有 $1 \le i < j \le m$，满足 $a_i \neq a_j$ 或 $b_i \neq b_j$。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^3$。

输出格式

对于每组测试数据，输出一行，包含一个长度为 $n$ 的字符串。如果可能为每个元素赋值，使得所有关系都得到满足且第 $i$ 个元素是中位数，则字符串的第 $i$ 个字符应为 '1'，否则为 '0'。

样例

样例输入 1

2
5 4
1 2
3 2
2 4
2 5
3 2
1 1
2 3

样例输出 1

01000
000

说明

对于第一个样例测试数据，由于第 2 个元素小于第 1 个和第 3 个元素，且大于第 4 个和第 5 个元素，因此第 2 个元素是有可能成为中位数的。

对于第二个样例测试数据，由于第 1 个元素不可能大于它自身，因此不可能为这些元素赋值以满足所有关系。