Little E has fallen in love with a game called "Meow". This game has a deck of cards and $n$ stacks from which elements can be removed from the bottom. The goal is to eliminate all cards according to the game rules.

Initially, there are $m$ cards in the deck. From top to bottom, the patterns on the cards are $a_1, a_2, \dots, a_m$. There are $k$ different patterns in total, numbered from $1$ to $k$. There is an even number of cards for each pattern in the deck. Initially, all stacks are empty.

This game has two types of operations:

• Choose a stack and place the card from the top of the deck onto the top of this stack. If, after this operation, the top two cards of this stack have the same pattern, these two cards will be automatically eliminated.
• Choose two different stacks. If the cards at the bottom of these two stacks have the same pattern, these two cards can be eliminated, and the card directly above the bottom card in each stack will become the new bottom card. If the patterns are different, nothing happens.

There are $T$ levels in this game, and Little E has been unable to pass them. Please help Little E design a game plan, i.e., for each level of the game, provide a sequence of operations that allows Little E to eliminate all the cards.

Input Format

The first line contains a single positive integer $T$, representing the number of test cases.

For each test case:

The first line contains three positive integers $n, m, k$, representing the number of stacks, the number of cards, and the number of card patterns, respectively.

The second line contains $m$ positive integers $a_1, a_2, \dots, a_m$, representing the patterns of the cards in the deck from top to bottom.

It is guaranteed that a solution always exists.

Output Format

For each test case, output several lines.

The first line contains a single positive integer $op$, representing the number of operations. You must ensure that $m \le op \le 2 \times m$.

Each of the next $op$ lines contains two or three space-separated positive integers.

• If there are two integers 1 s, it means performing the first operation on stack $s$.
• If there are three integers 2 s1 s2, it means performing the second operation on stacks $s_1$ and $s_2$.

You must ensure that $1 \le s, s_1, s_2 \le n$, and $s_1 \neq s_2$.

Examples

Input 1

1
2 4 2
1 2 1 2

Output 1

5
1 1
1 1
1 2
2 1 2
1 1

Note

The following figure shows the initial state:

The following figure shows the state after the first two operations:

The following figure shows the state after the third and fourth operations:

The following figure shows the state after the fifth operation:

Example 2

See meow2.in and meow2.ans in the player's directory.

Constraints

Let $S$ be the sum of $m$ over all $T$ test cases.

For all test cases, it is guaranteed that $S \le 2 \times 10^6$, $1 \le n \le 300$, $1 \le a_i \le k$.

Scoring Method

For each test case, if after performing all operations in order, the deck is empty and all stacks are empty, your answer for this test case is considered correct.

Hint

You can determine which class of data a test point belongs to by the last digit of $T$.

Your output does not need to match the sample output; any valid solution will receive full points.

When hacking, $T$ can be any integer in $[1, 1\,005]$. You must ensure that $2n-2 \le k \le 2n-1$.