Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill: 

  * the graph contains exactly 2n + p edges; 
  * the graph doesn't contain self-loops and multiple edges; 
  * for any integer k (1 ≤ k ≤ n), any subgraph consisting of k vertices contains at most 2k + p edges. 



A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices. 

Your task is to find a p-interesting graph consisting of n vertices.

Input

The first line contains a single integer t (1 ≤ t ≤ 5) — the number of tests in the input. Next t lines each contains two space-separated integers: n, p (5 ≤ n ≤ 24; p ≥ 0; <image>) — the number of vertices in the graph and the interest value for the appropriate test. 

It is guaranteed that the required graph exists.

Output

For each of the t tests print 2n + p lines containing the description of the edges of a p-interesting graph: the i-th line must contain two space-separated integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — two vertices, connected by an edge in the resulting graph. Consider the graph vertices numbered with integers from 1 to n. 

Print the answers to the tests in the order the tests occur in the input. If there are multiple solutions, you can print any of them.

Examples

Input

1
6 0


Output

1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class A {

	void run() throws IOException {
		int t = ni();
		while (--t >= 0) {
			int n = ni(), p = ni();

			boolean[][] q = new boolean[n][n];
			int[] deg = new int[n];
			for (int i = 0; i < n; i++) {
				Arrays.fill(q[i], true);
				deg[i] = n - 1;
				q[i][i] = false;
			}

			for (int i = (n * (n - 1)) / 2; i > 2 * n + p; i--) {
				int maxdeg = 0;
				for (int j = 1; j < n; j++) {
					if (deg[j] > deg[maxdeg]) {
						maxdeg = j;
					}
				}
				int pair = 0;
				for (int j = 0; j < n; j++) {
					if (q[maxdeg][j]) {
						pair = j;
					}
				}
				for (int j = 0; j < n; j++) {
					if (q[maxdeg][j] && deg[j] > deg[pair]) {
						pair = j;
					}
				}
				deg[pair]--;
				deg[maxdeg]--;
				q[pair][maxdeg] = q[maxdeg][pair] = false;
			}
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					if (q[i][j]) {
						pw.println((i + 1) + " " + (j + 1));
					}
				}
			}

		}

	}

	int[][] nm(int a_len, int a_hei) throws IOException {
		int[][] _a = new int[a_len][a_hei];
		for (int i = 0; i < a_len; i++)
			for (int j = 0; j < a_hei; j++)
				_a[i][j] = ni();
		return _a;
	}

	String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	boolean hasNext() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = br.readLine();
			if (line == null) {
				return false;
			}
			st = new StringTokenizer(line);
		}
		return true;
	}

	int[] na(int a_len) throws IOException {
		int[] _a = new int[a_len];
		for (int i = 0; i < a_len; i++)
			_a[i] = ni();
		return _a;
	}

	int ni() throws IOException {
		return Integer.parseInt(next());
	}

	long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	String nl() throws IOException {
		return br.readLine();
	}

	void tr(String debug) {
		if (!OJ)
			pw.println(" " + debug);
	}

	static PrintWriter pw;
	static BufferedReader br;
	static StringTokenizer st;
	static boolean OJ;

	public static void main(String[] args) throws IOException {
		long timeout = System.currentTimeMillis();
		OJ = System.getProperty("ONLINE_JUDGE") != null;
		pw = new PrintWriter(System.out);
		br = new BufferedReader(OJ ? new InputStreamReader(System.in) : new FileReader(new File("A.txt")));
		while (br.ready())
			new A().run();
		if (!OJ) {
			pw.println();
			pw.println("----------------------------------");
			pw.println(System.currentTimeMillis() - timeout);
		}
		br.close();
		pw.close();
	}

}
