Problem Description

You are given $n$, and an array $[a_1,a_2,\dots,a_{n+1}]$ of length $n+1$. Initially, $a_i=i\ (1\le i\le n)$, and $a_{n+1}=0$.

You may only perform the following type of operation, by printing a specific string:

• Print i j: where $i,j$ are positive integers with $1\le i,j\le n+1$, meaning assign $a_i$ to $a_j$ (i.e., set $a_i=a_j$).

Please cyclically shift the first $n$ elements of array $a$ to the right by $K$ positions. That is, after all operations you print are executed, it must satisfy:

• For positions $i\ (1\le i\le K)$, $a_i = n-K+i$.
• For positions $i\ (K+1\le i\le n)$, $a_i = i-K$.
• The $(n+1)$-th element can be anything.

You may perform at most $T=\lfloor1.5n\rfloor$ assignment operations.

If you use more than $T$ operations, you can still get partial points. Specifically, let your number of operations be $S$:

• If $S\le T$, you get $100$ points.
• If $T<S\le 4T$, you get $50$ points.
• If $S>4T$, you get $0$ points.

Your score for this problem is the minimum score among all testdata in all test points.

Input Format

This problem contains multiple groups of data in a single test point.

The first line contains the number of data groups $T$.

For each data group:

The first line contains two positive integers $n,K$.

Output Format

For each data group:

Print the number of operations $k\ (0\le k\le 4T)$ on the first line. Note that you do not need to minimize $k$.

Then print $k$ lines, each containing two positive integers $i,j$, representing one operation. $(1\le i,j\le n+1)$.

2
3 0
2 1

0
3
3 1
1 2
2 3

Hint

All data satisfy: $1\le T\le 10^4$, $1\le n\le 10^5$, $0\le K\le n-1$. It is guaranteed that, within the same test point, the sum of all $n$ does not exceed $5\times 10^5$.

Translated by ChatGPT 5