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






public class Main {
    static Scanner input = new Scanner(System.in);
    final static double EPS = 1e-8;
    static char[][] arr1;
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[][] vis;
    static int n; 
    static int m; 
    static ArrayList<Integer> lengths;
    static int[] length;
    static Stack<Integer> s = new Stack<>();
    static ArrayList<Integer> topo;
    static int count;
    static char arr[][];
    static char[] charArr;
    static String word1;
    static int[][] d;
    static int[][] done;
    static long ans = 1;
    static char word[];
    static int[] d4x = {-1, 1, 0, 0};
    static int[] d4y = {0, 0, -1, 1};
    static int[] d8x = {-1, 1, 0, 0, 1, 1, -1, -1};
    static int[] d8y = {0, 0, -1, 1, 1, -1, 1, -1};
    static Queue<Point> q;
    static int mat[][];
    static String inp[][];

  
    
    
    public static long gcd(long a, long b) {
    	if (b == 0)
    		return a;
    	
    	return gcd(b, a % b);
    }
    
    
    
    public static void main(String[] args) {
    	int t = input.nextInt();
    	
    	for (int w = 0; w < t; w++) {
    		int n = input.nextInt();
    		int p = input.nextInt();
    		
    		int count = 0;
    		String ans = "";
    		boolean done = false;
    		for (int i = 1; i <= n; i++) {
    			for (int j = i + 1; j <= n; j++) {
    				ans += i + " " + j + "\n";
    				count++;
    				
    				if (count == 2 * n + p) {
    					done = true;
    					break;
    				}
    			}
    			if (done)
    				break;
    		}
    		
    		System.out.println(ans);
    	
    	}
    	
 
 
    }
    
    
    
    
    
    
    
    
    
    
    
}