#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool umax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long FIRSTTRUE(function<bool(long long)> f, long long lb, long long rb) {
  while (lb < rb) {
    long long mb = (lb + rb) / 2;
    f(mb) ? rb = mb : lb = mb + 1;
  }
  return lb;
}
long long LASTTRUE(function<bool(long long)> f, long long lb, long long rb) {
  while (lb < rb) {
    long long mb = (lb + rb + 1) / 2;
    f(mb) ? lb = mb : rb = mb - 1;
  }
  return lb;
}
template <class A>
void read(vector<A>& v);
template <class A, size_t second>
void read(array<A, second>& a);
template <class T>
void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template <class H, class... T>
void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template <class A>
void read(vector<A>& x) {
  for (auto& a : x) read(a);
}
template <class A, size_t second>
void read(array<A, second>& x) {
  for (auto& a : x) read(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
  string res;
  for (int i = 0; i < int((v).size()); i++) res += char('0' + v[i]);
  return res;
}
template <size_t second>
string to_string(bitset<second> b) {
  string res;
  for (int i = 0; i < second; i++) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string res;
  for (auto& x : v) {
    if (!f) res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}
template <class A>
void write(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void write(const H& h, const T&... t) {
  write(h);
  write(t...);
}
void print() { write("\n"); }
template <class H, class... T>
void print(const H& h, const T&... t) {
  write(h);
  if (sizeof...(t)) write(' ');
  print(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
template <class T>
void offset(long long o, T& x) {
  x += o;
}
template <class T>
void offset(long long o, vector<T>& x) {
  for (auto& a : x) offset(o, a);
}
template <class T, size_t second>
void offset(long long o, array<T, second>& x) {
  for (auto& a : x) offset(o, a);
}
mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
long long randint(long long a, long long b) {
  return uniform_int_distribution<long long>(a, b)(mt_rng);
}
template <class T, class U>
void vti(vector<T>& v, U x, size_t n) {
  v = vector<T>(n, x);
}
template <class T, class U>
void vti(vector<T>& v, U x, size_t n, size_t m...) {
  v = vector<T>(n);
  for (auto& a : v) vti(a, x, m);
}
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
long long absolute(long long a, long long b) { return max(a, b) - min(a, b); }
void solve() {
  vector<int> adj[30];
  vector<pair<int, int> > edges;
  int n, p;
  read(n);
  read(p);
  for (int i = 0; i < n; i++) {
    for (int loop = 0; loop < 4; loop++) {
      int minimum_size = 400;
      int from = 0;
      int to = 0;
      if (int((adj[i]).size()) == 4) continue;
      for (int l = 0; l < n; l++) {
        if (i == l) continue;
        if (int((adj[l]).size()) == 4) continue;
        bool already = false;
        for (auto k : adj[l])
          if (k == i) already = true;
        if (already) continue;
        if (minimum_size >= int((adj[l]).size())) {
          minimum_size = int((adj[l]).size());
          from = min(i, l);
          to = max(i, l);
        }
      }
      adj[to].push_back(from);
      adj[from].push_back(to);
      edges.push_back({from, to});
    }
  }
  for (int i = 0; i < p; i++) {
    int from = 0;
    int to = 0;
    for (int l = 0; l < n; l++) {
      for (int j = 0; j < n; j++) {
        if (l == j) continue;
        bool already = false;
        for (auto k : adj[l])
          if (k == j) already = true;
        if (already) continue;
        from = l;
        to = j;
      }
    }
    adj[from].push_back(to);
    adj[to].push_back(from);
    edges.push_back({min(to, from), max(to, from)});
  }
  sort((edges).begin(), (edges).end());
  for (int i = 0; i < int((edges).size()); i++)
    cout << edges[i].first + 1 << " " << edges[i].second + 1 << "\n";
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  read(t);
  for (int i = 0; i < t; i++) solve();
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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>
bool umin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool umax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long FIRSTTRUE(function<bool(long long)> f, long long lb, long long rb) {
  while (lb < rb) {
    long long mb = (lb + rb) / 2;
    f(mb) ? rb = mb : lb = mb + 1;
  }
  return lb;
}
long long LASTTRUE(function<bool(long long)> f, long long lb, long long rb) {
  while (lb < rb) {
    long long mb = (lb + rb + 1) / 2;
    f(mb) ? lb = mb : rb = mb - 1;
  }
  return lb;
}
template <class A>
void read(vector<A>& v);
template <class A, size_t second>
void read(array<A, second>& a);
template <class T>
void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template <class H, class... T>
void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template <class A>
void read(vector<A>& x) {
  for (auto& a : x) read(a);
}
template <class A, size_t second>
void read(array<A, second>& x) {
  for (auto& a : x) read(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
  string res;
  for (int i = 0; i < int((v).size()); i++) res += char('0' + v[i]);
  return res;
}
template <size_t second>
string to_string(bitset<second> b) {
  string res;
  for (int i = 0; i < second; i++) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string res;
  for (auto& x : v) {
    if (!f) res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}
template <class A>
void write(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void write(const H& h, const T&... t) {
  write(h);
  write(t...);
}
void print() { write("\n"); }
template <class H, class... T>
void print(const H& h, const T&... t) {
  write(h);
  if (sizeof...(t)) write(' ');
  print(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
template <class T>
void offset(long long o, T& x) {
  x += o;
}
template <class T>
void offset(long long o, vector<T>& x) {
  for (auto& a : x) offset(o, a);
}
template <class T, size_t second>
void offset(long long o, array<T, second>& x) {
  for (auto& a : x) offset(o, a);
}
mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
long long randint(long long a, long long b) {
  return uniform_int_distribution<long long>(a, b)(mt_rng);
}
template <class T, class U>
void vti(vector<T>& v, U x, size_t n) {
  v = vector<T>(n, x);
}
template <class T, class U>
void vti(vector<T>& v, U x, size_t n, size_t m...) {
  v = vector<T>(n);
  for (auto& a : v) vti(a, x, m);
}
const int d4i[4] = {-1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
long long absolute(long long a, long long b) { return max(a, b) - min(a, b); }
void solve() {
  vector<int> adj[30];
  vector<pair<int, int> > edges;
  int n, p;
  read(n);
  read(p);
  for (int i = 0; i < n; i++) {
    for (int loop = 0; loop < 4; loop++) {
      int minimum_size = 400;
      int from = 0;
      int to = 0;
      if (int((adj[i]).size()) == 4) continue;
      for (int l = 0; l < n; l++) {
        if (i == l) continue;
        if (int((adj[l]).size()) == 4) continue;
        bool already = false;
        for (auto k : adj[l])
          if (k == i) already = true;
        if (already) continue;
        if (minimum_size >= int((adj[l]).size())) {
          minimum_size = int((adj[l]).size());
          from = min(i, l);
          to = max(i, l);
        }
      }
      adj[to].push_back(from);
      adj[from].push_back(to);
      edges.push_back({from, to});
    }
  }
  for (int i = 0; i < p; i++) {
    int from = 0;
    int to = 0;
    for (int l = 0; l < n; l++) {
      for (int j = 0; j < n; j++) {
        if (l == j) continue;
        bool already = false;
        for (auto k : adj[l])
          if (k == j) already = true;
        if (already) continue;
        from = l;
        to = j;
      }
    }
    adj[from].push_back(to);
    adj[to].push_back(from);
    edges.push_back({min(to, from), max(to, from)});
  }
  sort((edges).begin(), (edges).end());
  for (int i = 0; i < int((edges).size()); i++)
    cout << edges[i].first + 1 << " " << edges[i].second + 1 << "\n";
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  read(t);
  for (int i = 0; i < t; i++) solve();
  return 0;
}

```