#454 Permutations and Queries

Statement

Statement language

A permutation $P=[P_1,P_2,\cdots,P_N]$ of length $N$ is given.

In one reversal, choose two integers $l,r$ satisfying both conditions below.

$1 \leq l \leq r \leq N$ .
$r-l+1 \geq \left\lceil\cfrac{N}{2}\right\rceil-1$ .

Then reverse the order of the contiguous segment $P_l,P_{l+1},\cdots,P_r$ .

Sort $P$ in increasing order using at most $3N$ reversals, and print the reversals you used.

Input

The input is given from Standard Input in the following format:

$T$ case $_1$ case $_2$

Output

For each test case, print the number $Q$ of reversals on the first line.

Then print $Q$ lines. On the $i$ -th line, print the two integers $l_i,r_i$ chosen for the -th reversal.

Constraints

$1 \leq T \leq 100$ .
$2 \leq N \leq 2\,000$ .
$P$ is a permutation of .

Subtasks

#	Score	Constraints
1	18	$N \leq 7$ .
2	29	$N \leq 200$ .
3	53	No additional constraints.

Samples

Input

Output

In the first test case, every printed interval has length at least $1$ . In the second test case, every printed interval has length at least $2$ . Applying the printed reversals in order sorts both permutations.