You guys must have solved lots of problems, but ever wondered how test cases for those problems are created?
In this problem, you have to create test cases for a graph problem.

Given N and M, you have to make an undirected graph containing N nodes and M edges. But this graph should satisfy additional property - For every edge of this graph, one endpoint should have odd degree and other endpoint should have even degree. There should be no self - loops or parallel edges in this graph. It's not necessary for the graph to be connected.

Note that, degree of any node U in the graph is defined as total number of edges having U as one of its endpoint.

INPUT:
First line of input will consist of integer T denoting total number of test cases. Each test case will consist of two integers N and M denoting total number of nodes and edges required in the graph.

OUTPUT:
For each test case,you have to print M lines if such a graph is possible. Each line should contain two integers denoting the endpoints of edge. If there are many possible solutions, you can print any of them. Print 1 if it's not possible to make such a graph.

CONSTRAINTS:
\(1 ≤ T ≤ 10\)
\(2 ≤ N ≤ 10^5 \)
\(1 ≤ M ≤ 10^5\)