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.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		
		Scan scan = new Scan();
		int t,n,p;
		t = scan.nextInt();
		while(t-- != 0){
			n = scan.nextInt();
			p = scan.nextInt();
			boolean[][] matrix = new boolean[n][n];
			Vertex[] count = new Vertex[n];
			for(int i=0;i<n;i++) count[i] = new Vertex(i+1);
			for(int i=0;i<2*n+p;i++){
				int min1,min2=0;
				Arrays.sort(count);
				min1 = count[0].id;
				for(int j=1;j<n;j++){
					min2 = count[j].id;
					if(matrix[min1-1][min2-1] == false){
						count[0].value++;
						count[j].value++;
						break;
					}
				}
				matrix[min1-1][min2-1] = matrix[min2-1][min1-1] = true;
				
				System.out.println(min1+" "+min2);
			}
		}
	}
	
	static class Vertex implements Comparable<Vertex>{
		int id,value;
		Vertex(int id){
			this.id = id;
			value = 0;
		}
		@Override
		public int compareTo(Vertex rhs) {
			if(value < rhs.value) return -1;
			else if(value == rhs.value) return 0;
			else return 1;
		}
		
	}
	
	static int findmin(int[] arr){
		int min = Integer.MAX_VALUE,result = 0;
		for(int i=0;i<arr.length;i++){
			if(arr[i] < min){
				min = arr[i];
				result = i;
			}
		}
		//arr[result]++;
		return result;
	}

}

class Scan{

	BufferedReader buffer;
	StringTokenizer tok;

	public Scan(){
		buffer = new BufferedReader(new InputStreamReader(System.in));
	}

	boolean hasNext(){
		while(tok == null || !tok.hasMoreElements()){
			try{
				tok = new StringTokenizer(buffer.readLine());
			}catch(Exception e){
				return false;
			}
		}
		if(tok == null) return false;
		return true;
	}

	String next(){
		if(hasNext()) return tok.nextToken();
		return null;
	}

	String nextLine(){
		if(hasNext()) return tok.nextToken("\n\r");
		return null;
	}

	int nextChar(){
		try{
			return buffer.read();
		}catch(Exception e){
		}
		return -1;
	}

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

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

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

}