#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void remax(T& A, T B) {
  if (A < B) A = B;
}
template <class T>
inline void remin(T& A, T B) {
  if (A > B) A = B;
}
string ToString(long long num) {
  string ret;
  do {
    ret += ((num % 10) + '0');
    num /= 10;
  } while (num);
  reverse(ret.begin(), ret.end());
  return ret;
}
long long ToNumber(string s) {
  long long r = 0, p = 1;
  for (int i = s.size() - 1; i >= 0; --i) r += (s[i] - '0') * p, p *= 10;
  return r;
}
long long Gcd(long long a, long long b) {
  while (a %= b ^= a ^= b ^= a)
    ;
  return b;
}
long long Power(long long base, long long power) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret *= base;
    power >>= 1;
    base *= base;
  }
  return ret;
}
long long PowerMod(long long base, long long power, long long mod) {
  if (!power) return 1;
  if (power & 1) return (base * PowerMod(base, power - 1, mod)) % mod;
  return PowerMod((base * base) % mod, power >> 1, mod);
}
int Log(long long num, long long base) {
  int ret = 0;
  while (num) {
    ++ret;
    num /= base;
  }
  return ret;
}
int Count(long long mask) {
  int ret = 0;
  while (mask) {
    if (mask & 1) ++ret;
    mask >>= 1;
  }
  return ret;
}
inline void run() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, p, a = 1, b = 2;
    scanf("%d%d", &n, &p);
    p += n * 2;
    while (p--) {
      printf("%d %d\n", a, b++);
      if (b > n) b = ++a + 1;
    }
  }
}
int main() {
  FILE* input = stdin;
  FILE* output = stdout;
  while (!feof(input)) {
    run();
    break;
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void remax(T& A, T B) {
  if (A < B) A = B;
}
template <class T>
inline void remin(T& A, T B) {
  if (A > B) A = B;
}
string ToString(long long num) {
  string ret;
  do {
    ret += ((num % 10) + '0');
    num /= 10;
  } while (num);
  reverse(ret.begin(), ret.end());
  return ret;
}
long long ToNumber(string s) {
  long long r = 0, p = 1;
  for (int i = s.size() - 1; i >= 0; --i) r += (s[i] - '0') * p, p *= 10;
  return r;
}
long long Gcd(long long a, long long b) {
  while (a %= b ^= a ^= b ^= a)
    ;
  return b;
}
long long Power(long long base, long long power) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret *= base;
    power >>= 1;
    base *= base;
  }
  return ret;
}
long long PowerMod(long long base, long long power, long long mod) {
  if (!power) return 1;
  if (power & 1) return (base * PowerMod(base, power - 1, mod)) % mod;
  return PowerMod((base * base) % mod, power >> 1, mod);
}
int Log(long long num, long long base) {
  int ret = 0;
  while (num) {
    ++ret;
    num /= base;
  }
  return ret;
}
int Count(long long mask) {
  int ret = 0;
  while (mask) {
    if (mask & 1) ++ret;
    mask >>= 1;
  }
  return ret;
}
inline void run() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, p, a = 1, b = 2;
    scanf("%d%d", &n, &p);
    p += n * 2;
    while (p--) {
      printf("%d %d\n", a, b++);
      if (b > n) b = ++a + 1;
    }
  }
}
int main() {
  FILE* input = stdin;
  FILE* output = stdout;
  while (!feof(input)) {
    run();
    break;
  }
  return 0;
}

```