#587 Ladders and Queries

Statement

Statement language

A ladder has $N$ vertical bars, numbered from $1$ to $N$ from left to right. Heights where horizontal rungs may be placed are numbered from $1$ to $2N-2$ from top to bottom. Initially, there are no rungs.

To traverse the ladder, start at the top of one vertical bar and move downward. Whenever you encounter a horizontal rung connected to the current bar, follow the rung to the adjacent bar, then continue moving downward. Repeat this process until you reach the bottom of the ladder.

You may perform the following two operations:

$1\ h\ x$ : Toggle the rung joining bars $x$ and $x+1$ at height $h$ . Create it if it is absent, or erase it if it is present. $(1 \leq h \leq 2 N - 2, 1 \leq x \leq N - 1)$

Two rungs at the same height may not share a bar. Therefore, this condition must still hold after a type- $1$ operation creates a rung. If $N=1$ , no rung can be placed and no type- $1$ operation is allowed.

You are given $N$ target pairs $(a_1,b_1),(a_2,b_2),\cdots,(a_N,b_N)$ . Perform exactly type- operations in order so that the -th type- operation starts at bar and ends at bar . You may use at most type- operations over the entire sequence of operations.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, first print the total number of operations $K$ . Then print the $K$ operations in order, one per line. Each operation has the form $1\ h\ x$ or $2\ x$ .

There must be exactly $N$ type- operations. The -th must start on bar and end on bar . There may be at most type- operations. If there are multiple solutions, print any of them.

Constraints

$1 \leq T \leq 10\,000$ .
$1 \leq N \leq 2\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	11	$a_i=b_i$ ( $1\leq i\leq N$ ).

Samples

Input

Output

In the first case, the first type- $2$ operation goes from bar $1$ to bar $2$ , and the second goes from bar $2$ to bar $1$ . The second case needs no rung.