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
/*
 * Remember a 7.0 student can know more than a 10.0 student.
 * Grades don't determine intelligence, they test obedience. 
 * I Never Give Up.
 */
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.text.*;

import static java.lang.System.out;
import static java.util.Arrays.*;
import static java.lang.Math.*;
public class ContestMain {
	private static Reader in=new Reader();
	private static StringBuilder ans=new StringBuilder();
	private static long MOD=1000000007;//10^9+7 
//	private static final int N=100000; //10^5
//	private static final int LIM=26;
//	private static final double PI=3.1415;
//	private static ArrayList<Integer> v[]=new ArrayList[N];
//	private static int color[]=new int[N]; //For Graph Coloring
//	private static boolean mark[]=new boolean[N];
//	private static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//	private static void dfs(int node){mark[node]=true;for(int x:v[node]){if(!mark[x]){dfs(x,v);}}}
//	private static long powmod(long x,long n,long m){
//		if(n==0)return 1;
//		else if(n%2==0)return(powmod((x*x)%m,n/2,m));
//		else return (x*(powmod((x*x)%m,(n-1)/2,m)))%m;
//	}
//	private static void shuffle(long [] arr) {
//		for (int i = arr.length - 1; i >= 2; i--) {
//			int x = new Random().nextInt(i - 1);
//	        long temp = arr[x];
//	        arr[x] = arr[i];
//	        arr[i] = temp;
//	    }
//	 }
//	private static void swap(int i,int j,int ar[]){
//		int temp=ar[i];
//		ar[i]=ar[j];
//		ar[j]=temp;
//	}
//	private static long gcd(long a, long b){
//		if(b==0)return a;
//		return gcd(b,a%b);
//	}
//	private static boolean check(int x,int y){
//		if((x>=0&&x<n)&&(y>=0&&y<m)&&mat[x][y]!='X'&&!visited[x][y])return true;
//		return false;
//	}
	public static void main(String[] args) throws IOException{
		int t=in.nextInt();
		int n,p,temp;
		while(t-->0){
			n=in.nextInt();
			p=in.nextInt();
			temp=2*n+p;
			for(int i=1;i<=n&&temp>0;i++){
				for(int j=i+1;j<=n&&temp>0;j++){
					ans.append(i+" "+j+"\n");
					temp--;
				}
			}
		}
		out.println(ans);
	}
	static class Pair<T> implements Comparable<Pair>{
		int l;
		int r;
		int c;
		Pair(){
			l=0;
			r=0;
		}
		Pair(int k,int v,int p){
			l=k;
			r=v;
			c=p;
		}
		@Override
		public int compareTo(Pair o) {
			if(o.l!=l)return (int) (l-o.l);
			else return (r-o.r);
		}
		
	}
	static class Reader{
        BufferedReader br;
        StringTokenizer st;
        public Reader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
     
                	st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}