Little B likes graphs, especially undirected simple graphs with a relatively small number of edges.

Mother's Day is approaching, and Little B has drawn an undirected simple graph (i.e., no multiple edges or self-loops) on paper with $n$ nodes and $m$ edges. It is guaranteed that each node is adjacent to at most 7 other nodes. He wants to color the nodes of the graph with 4 different colors as a Mother's Day gift for his mother.

Little B wants the colored graph to be as beautiful as possible, and he thinks it looks bad if nodes of the same color are connected. Therefore, he hopes to color every pair of adjacent nodes with different colors. Unfortunately, Little B soon discovers that this is impossible for some graphs. He has to lower his requirements: among the nodes adjacent to any given node, at most one node can have the same color as it.

The constraints have been relaxed, making the problem simpler; however, Little B is busy with his major assignments, so he has come to you for help. Now, please tell Little B whether it is possible to color each node in the graph with an appropriate color that satisfies his requirements. If it is possible, please provide him with a coloring scheme; otherwise, you must cruelly tell Little B: impossble.

Input

The input contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10$), representing the number of test cases.

For each test case:

The first line contains two integers $n, m$ ($1 \le n \le 25000, 1 \le m \le 100000$), representing the number of nodes and edges in the graph, respectively (nodes are labeled starting from 1).

The next $m$ lines each contain two integers $x, y$ ($1 \le x, y \le n$), describing an edge in the graph. It is guaranteed that there are no multiple edges or self-loops.

It is guaranteed that in a single input file, $\sum n \le 200000$ and $\sum m \le 800000$.

Output

We label the four different colors with the lowercase English letters a, b, c, and d.

For each test case:

• If a solution exists, output a single string $S$ of length $n$, where $S_i$ represents the color you assigned to the $i$-th node (1-indexed).
• Otherwise, output impossble.

Examples

Input 1

1
8 28
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8

Output 1

abcdabcd