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; $2 n + p \leq \frac{n(n - 1)}{2}$) — 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 a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — 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

Difficulty: interview

Starter code:

Solutions:
t=int(input())
for tt in range(t):
    n,p=map(int,input().split())
    now=1
    ans=0
    while ans!=2*n+p:
        for i in range(now+1,n+1):
            if ans==2*n+p:
                break
            print(now,i)
            ans+=1
        now+=1

t = int(input())

while t > 0:
    [n, p] = map(int, input().split(' '))
    count = int(0)
    for i in range(n):
        j = i+2
        while j <= n:
            count = count+1
            print(str(i+1)+' '+str(j))
            if count == 2*n+p:
                break
            j = j + 1
        if j <= n:
            break
    t = t-1

import sys

def compute(n,p):
    count=0
    for i in range(1,n+1,1):
        for j in range(i+1,n+1,1):
            print('{0} {1}'.format(i,j))
            count += 1
            if(count >= (2*n+p)):
                return

t = int(input())
for case in range(t):
    n,p = list(map(int,input().split()))
    compute(n,p)


t = int(input())
while t > 0:
    t -= 1
    n, p = list(map(int, input().split()))
    count = 0
    for i in range(1, n):
        for j in range(i+1, n+1):
            count += 1
            if count <= 2*n + p:
                print("%s %s" % (i, j))


t = int(input())
for k in range(t):
    n, p = map(int, input().split())
    c = 0
    e = 2*n+p;
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if c < e:
               print(i, j)
               c += 1

t = int(input())
while t > 0:
    t -= 1
    n, p = map(int, input().split())
    count = 0
    for i in range(1, n):
        for j in range(i+1, n+1):
            count += 1
            if count <= 2*n + p:
                print("%s %s" % (i, j))

for t in range(int(input())):
    n, p = map(int, input().split())
    i, j = 1, 2
    for k in range(2 * n + p):
        print(i, j)
        j += 1
        if j > n:
            i += 1
            j = i + 1

t = int(input())
for z in range(t):
    n, p = [int(x) for x in input().split()]
    cur = 0
    for i in range(1, n):
        j = i + 1
        while (j <= n) and (cur < n*2 + p):
            print(i, j)
            j += 1
            cur += 1

N = int(input())

for i in range(N):
    a = list(map(int,input().split()))
    c = 0
    for i in range(a[0]):
        if c == 2*a[0]+a[1]:
            break
        for j in range(i+1,a[0]):
            if c == 2*a[0]+a[1]:
                break
            print(i+1,j+1)
            c = c+1


t = int(input())
while t > 0:
    t -= 1
    n, p = list(map(int, input().split()))
    num = 0
    for i in range(1, n):
        for j in range(i+1, n+1):
            num += 1
            if num <= 2*n + p:
                print(i,j)


t = int(input())
while(t > 0):
	n, p = list(map(int, input().split()))
	temp = 2 * n + p
	l = 1
	r = l + 1
	while(temp > 0):
		if(r == n + 1):
			l += 1
			r = l + 1
		print(l,r)
		r += 1
		temp -= 1
	t -= 1


a = int(input())
l = []
for j in range(a):
	start = 1
	end = 1
	h = list(map(int, input().split()))
	n = h[0]
	p = h[1]
	for i in range(2 * n + p):
		if (end + 1 > n):
			start += 1
			end = start + 1
		else:
			end += 1
		print(start, end)




t = int(input())
for z in range(t):
    n, p = [int(x) for x in input().split()]
    cur = 0
    for i in range(1, n):
        j = i + 1
        while (j <= n) and (cur < n*2 + p):
            print(i, j)
            j += 1
            cur += 1

t=int(input())

def readints():
  return map(int, input().split(' '))

def solve():
  n,p=readints()
  # 2n-3
  viz = [ [0]*n for _ in range(n) ]
  for j in range(n):
    viz[0][j]=viz[j][0]=1
  for j in range(n):
    viz[1][j]=viz[j][1]=1
  # p+3
  leftover=p+3
  done=False
  for i in range(n):
    if done: break
    for j in range(i+1,n):
      if viz[i][j]==1: continue
      leftover-=1
      viz[i][j]=viz[j][i]=1
      if leftover==0: 
        done=True
        break
  for i in range(n):
    for j in range(i+1,n):
      if viz[i][j]:
        print(i+1,j+1)
for _ in range(t):
  solve()

'''input
1
6 0
'''
# practicing a skill right after sleep improves it a lot quickly
from sys import stdin, setrecursionlimit


# main starts
t = int(stdin.readline().strip())
for _ in range(t):
	n, p = list(map(int, stdin.readline().split()))
	count = 0
	flag = 0
	for i in range(1, n + 1):
		if flag == 1:
			break
		for j in range(i + 1, n + 1):
			if count == 2 * n + p:
				flag = 1
				break
			print(i, j)
			count += 1



def solve(n, p):
    cnt = 2 * n + p
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            print(i, j)
            cnt -= 1
            if cnt == 0:
                return

def main():
    t = int(input())
    for _ in range(t):
        n, p = map(int, input().split())
        solve(n, p)

        

def __starting_point():
    main()
__starting_point()

import sys
     
def get_ints(): return map(int, sys.stdin.readline().strip().split())

t = int(input())
while t:
    flag = 0
    n,p = get_ints()
    count = 0
    i = 1
    while i<(n+1):
        for j in range(i+1,n+1):
            print(i,j)
            count+=1
            if count==2*n+p:
                flag = 1
                break
        if flag==1:
            break
        i+=1
    t-=1