import java.io.*;
import java.util.*;

public class TestsGen {

	static class Pair {
		int first, second;

		public Pair() {
			super();
			this.first = 0;
			this.second = 0;
		}

		public Pair(int first, int second) {
			super();
			this.first = first;
			this.second = second;
		}
	}

	static int done = 0;
	static ArrayList<Pair> data = new ArrayList<Pair>();
    static ArrayList<Character> s = new ArrayList<Character>();
	static final Random rand = new Random(556668949239L);

	static void print(int n, int m) throws IOException {
		done++;
		System.err.println(done);
		PrintWriter out;
		if (done < 10)
			out = new PrintWriter("0" + String.valueOf(done));
		else
			out = new PrintWriter("" + String.valueOf(done));
		out.println(n + " " + m);
		for (int i = 0; i < m; i++) {
			out.println(data.get(i).first + " " + data.get(i).second);
		}
		data.clear();
		out.close();
	}

	static void genString(int n) throws IOException {
		s.clear();
		int bal = 0;
		for (int i = 0; i < n; i++)
			if (bal == 0) {
				s.add('(');
				bal++;
			} else {
				if (bal == n - i) {
					s.add(')');
					bal--;
				} else if (rand.nextBoolean()) {
					s.add(')');
                    bal--;
				} else {
					s.add('(');
					bal++;
				}
			}
	}

	static void genZap() throws IOException {
		Stack<Integer> pos = new Stack<Integer>();
		for (int i = 0; i < s.size(); i++) {
			if (s.get(i) == '(') {
				pos.push(i + 1);
			} else {
				data.add(new Pair(pos.pop(), i + 1));
			}
		}
	}

	static void genRand(int n, int m) throws IOException {
	    genString(n);
		genZap();
		Collections.shuffle(data, rand);
		print(n, m);
		return;
	}

	public static void main(String[] args) throws IOException {
        // n <= 1000
		genRand(10, 2);
        genRand(10, 5);
        genRand(100, 23);
        genRand(100, 42);
        genRand(500, 123);
        genRand(500, 250);
        genRand(666, 239);
        genRand(1000, 500);
        genRand(1000, 420);
        genRand(1000, 500);
        
        // n <= 100000
        genRand(100000, 50000);
        genRand(100000, 50000);
        genRand(100000, 50000);
        for (int i = 13; i < 20; i++)
            genRand(i * 5000, i * 2398);
		return;
	}
}
