NIO has a tree rooted at .

He defines the hash function of  as , where  and  is the lowest common ancestor of and .

Unfortunately, he lost the tree in an accident. The only thing he remembers is .

Now given and , you need to reconstruct  with no more than vertices.

输入描述:

The first line contains an integer  indicating the number of test cases.

For each test case, the only line contains four integers .

It is guarenteed that  are chosen randomly from range .

输出描述:

For each test case, output  lines, where  is the number of vertices of the tree.

The first line output . You should make sure that .

The next  lines output two integers  indicating an edge in your tree. These  edges should form a tree.

1
36 2 3 2

2
1 2