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
def complete_graph(A, n):
  for i in xrange(1, n+1):
    for j in xrange(1,n+1):
      A[i][j] = 1

  return A

def finish_graph(v, A, edges_left):
  """n is the number of vertices in the complete graph"""
  i = 1
  while edges_left > 0:
    A[v][i] = 1
    A[i][v] = 1
    edges_left -= 1
    i += 1
  return A

def add_scaffold(vertices, A, n):
  last = n
  for v in vertices:
    A[v][1] = 1
    A[1][v] = 1

    A[v][last] = 1
    A[last][v] = 1

  return A

t = int(raw_input())
for i in xrange(0, t):
  n, p = map(int, raw_input().split(' '))

  dn = 0 #perfect size for graph
  for dne in xrange(4, 25):
    if ((dne * (dne-1))) >= 2*(2*dne + p):
      dn = dne
      break

  edges_left = 2*dne + p
  #print "Edges left (1): ", edges_left
  A = []
  for i in xrange(0, n+1):
    row = []
    for j in xrange(0, n+1):
      row.append(0)
    A.append(row)

  A = complete_graph(A, dne-1)
  edges_left -= ((dne-1) * (dne-2))/2
  #print "Edges left: ", edges_left
  A = finish_graph(dne, A, edges_left)

  vertices = list(range(dne+1, n+1))
  A = add_scaffold(vertices, A, dne)

  for i in xrange(1, (n+1)):
    for j in xrange(i+1, n+1):
      if A[i][j] == 1:
        print "%d %d" % (i, j)
