A function c mapping the set of vertices of a graph G into integers 1,...,k is called a k-coloring of G if for every pair of adjacent vertices u,v we have that c(u) is not equal to c(v). Find 6-coloring of a given planar graph.

Input

The first line contains an integer 1<=t<=100 denoting the number of test cases. Then, t planar graphs are given. Each graph is described by two lines. First line contains a string of the form:

Graph with n nodes and m edges:

The second line gives the edges of the graph separated with commas. Each edge is given as a pair of vertices: {u,v}. Vertices of the graph are denoted with integers 0...,n-1.

Output

For each test case print a 6-coloring of the corresponding planar graph. The coloring of a graph with n vertices shoud be given in n lines, where each line contains two integers

v c(v)

the number of a vertex and the color assigned to this vertex.

Example

Input:
2
Graph with 3 nodes and 3 edges:
{0,1},{1,2},{2,0}
Graph with 9 nodes and 14 edges:
{0,1},{0,2},{0,5},{0,8},{1,2},{2,3},{2,4},{3,4},{4,5},{4,8},{5,6},{5,7},{5,8},{6,7}

Output:
0 1
1 2
2 3

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

Hints

The SL algorithm (Smallest Last) solves the problem

Some tests are here