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 static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 

public class Template {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

	int nextInt() {
		return Integer.parseInt(next()); 
	}

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

	double nextDouble() {
		return Double.parseDouble(next());
	}

	int[] a; 
	int n,m; 
	Tree[] t; 
	class Tree {
		int[] le, ri; 
		long[] s; 
		boolean[] all; 

		public Tree(int n) {
	//		a = new int[4 * n]; 
			le = new int[4 * n]; 
			ri = new int[4 * n]; 
			s = new long[4 * n]; 
			all = new boolean[4 * n]; 
		}

		public void update(int p, int v) {
			update(1, 1, n, p, v);
		}

		public void update(int v, int l, int r, int p, int val) {
			if (l > p || r < p) return;
			if (l == r) {
				//a[v] = val; 
				if (val == 1) le[v] = 1; else le[v] = 0; 
				if (val == 1) ri[v] = 1; else ri[v] = 0; 
				if (val == 1) s[v] = 1; else s[v] = 0; 
				if (val == 1) all[v] = true; else all[v] = false; 
				return;
			}
			int m = (l+r) / 2; 
			update(v*2, l, m, p, val);
			update(v*2+1, m+1, r, p, val);
			long sl = s[v*2] - ri[v*2]*(ri[v*2] + 1L)/2; 
			long sr = s[v*2+1] - le[v*2+1]*(le[v*2+1] + 1L)/2; 
			long mid = ri[v*2] + le[v*2+1]; 
			mid = mid * (mid + 1L) / 2; 
			s[v] = sl + sr + mid; 
			all[v] = all[v*2] & all[v*2+1];
			ri[v] = ri[v*2+1] + (all[v*2+1] ? ri[v*2] : 0); 
			le[v] = le[v*2] + (all[v*2] ? le[v*2+1] : 0); 
		}
	}

	int bit(int x, int p) {
		if ((x & (1 << p)) > 0) return 1; else return 0;
	}

	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		Long start = System.currentTimeMillis();
			int t = nextInt(); 

			for (int q=0; q<t; q++) {
				int n = nextInt(); 
				int p = nextInt(); 

				int[][] a = new int[n][n]; 

				for (int i=0; i<n; i++) {
					a[i][(i+1) % n] = 1; 
					a[(i+1) % n][i] = 1; 
				}
				for (int i=0; i<n; i++) {
				 	a[i][(i+2) % n] = 1; 
				 	a[(i+2) % n][i] = 1; 
				}

				for (int i=0; i<p; i++) {
					for (int j=0; j<n; j++) {
						for (int k=j+1; k<n; k++) if (a[j][k] == 0) {
							a[j][k] = 1; 
							a[k][j] = 1; 
							j=n; 
							break; 
						}
					}
				}

				for (int i=0; i<n; i++)
					for (int j=i+1; j<n; j++) if (a[i][j]>0) {
						out.println((i+1) + " "  + (j+1));
					}
			}
		Long end = System.currentTimeMillis();

		//System.out.println((end - start) / 1000.0);
		out.close(); 
	}

	public static void main(String[] args) throws Exception {
		new Template().run(); 
	}
}                                      