Given a simple directed graph $G$ with $n$ vertices and $m$ edges, where vertices are numbered from $1$ to $n$. A simple directed graph is defined as a directed graph with no multiple edges or self-loops.

A vertex $r$ is defined as a root of the directed graph $G$ if and only if for every $1 \le k \le n$, there exists exactly one directed simple path from $r$ to $k$. A simple path is defined as a path that does not pass through any repeated vertices.

The types of each vertex are defined as follows: If vertex $r$ is a root of graph $G$, then $r$ is called a type-1 vertex of $G$. If vertex $r$ is not a type-1 vertex of $G$, and there exists a way to delete some edges such that the resulting graph $G'$ satisfies: all type-1 vertices of $G$ are roots of $G'$, and vertex $r$ is also a root of $G'$, then $r$ is called a type-2 vertex of $G$. * If vertex $r$ does not satisfy the above conditions, then $r$ is called a type-3 vertex of $G$.

According to the above definitions, every vertex of $G$ belongs to exactly one of the three types. You need to determine the type of each vertex from $1$ to $n$.

Input

Read data from the file graphee.in.

This problem contains multiple test cases. The first line contains a non-negative integer $c$, representing the test case ID. $c = 0$ indicates that this test case is a sample. The second line contains a positive integer $t$, representing the number of test cases.

For each test case: The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in the directed graph, respectively. The next $m$ lines each contain two positive integers $u$ and $v$, representing a directed edge from $u$ to $v$. It is guaranteed that $1 \le u, v \le n$, and the given directed graph $G$ contains no multiple edges or self-loops.

Output

Output to the file graphee.out.

For each test case, output a single string $s$ of length exactly $n$, representing the type of each vertex. Here, $s_i = 1$ means vertex $i$ is a type-1 vertex, $s_i = 2$ means vertex $i$ is a type-2 vertex, and $s_i = 3$ means vertex $i$ is a type-3 vertex.

Examples

Input 1

0
2
4 7
2 1
4 1
1 4
2 3
3 4
2 4
4 3
4 5
1 2
2 3
2 4
3 1
4 3

Output 1

3233
2211

Note

The sample contains two test cases.

For the first test case, the input graph is as follows:

Since there are no paths from $1, 3, 4$ to $2$, $1, 3, 4$ are all type-3 vertices. Since there are three directed simple paths from $2$ to $1$: $2 \to 1$, $2 \to 4 \to 1$, and $2 \to 3 \to 4 \to 1$, $2$ is not a type-1 vertex. After deleting edges $1 \to 4$, $4 \to 1$, $3 \to 4$, and $4 \to 3$, the directed simple paths from $2$ to $1, 3, 4$ are all unique, so $2$ is a root of $G'$, meaning $2$ is a type-2 vertex.

For the second test case, the input graph is as follows:

It is easy to see that $3, 4$ are both type-1 vertices. After deleting edge $2 \to 3$, the directed simple paths from each vertex to all other vertices are unique, so $1, 2$ are both type-2 vertices.

Examples

Input 2

见选手目录下的 graphee/graphee2.in

Output 2

见选手目录下的 graphee/graphee2.ans

Input 3

见选手目录下的 graphee/graphee3.in

Output 3

见选手目录下的 graphee/graphee3.ans

Input 4

见选手目录下的 graphee/graphee4.in

Output 4

见选手目录下的 graphee/graphee4.ans

Input 5

见选手目录下的 graphee/graphee5.in

Output 5

见选手目录下的 graphee/graphee5.ans

Input 6

见选手目录下的 graphee/graphee6.in

Output 6

见选手目录下的 graphee/graphee6.ans

Constraints

For all test cases, it is guaranteed that $1 \le t \le 10$, $2 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$, and the graph $G$ contains no multiple edges or self-loops.

Special Property A: Guaranteed that there are no type-1 vertices. Special Property B: Guaranteed that there are no type-2 vertices. Special Property C: Guaranteed that the vertex numbered 1 is a type-1 vertex of graph $G$.