Vasylko was given cubes with numbers from to . One cube had the number , two cubes had the number n-1, and so on, with n-1 cubes having the number , and cubes having the number .
He arranged the cubes in a square frame without a top boundary, so that all cubes were placed below the diagonal that runs from the top left corner to the bottom right corner. In the first column on the left, there are cubes with the number ; in the second column, there are n-1 cubes with the number ... in the -th column, there is one cube with the number . That is, in the -th column, there are n-i+1 cubes with the number .
Initial state
Vasylko wanted to rearrange them so that all cubes were positioned below the opposite diagonal. Thus, in the first row from the bottom, there should be cubes with the number ; in the second row, there should be n-1 cubes with the number ... in the -th row, there should be one cube with the number . That is, in the -th row, there should be n-i+1 cubes with the number .
Final state
He also decided that he would only move cubes from the top of one column to the top of another (not necessarily adjacent). Help him do this in the most efficient way — find the minimum number of moves he needs and output which moves Vasylko should make.
You can earn partial points; see details below.
The first line contains one integer (3 \le n \le 1000) — the size of the square.
In the first line, output one integer (1 \leq k \leq 10^6) — the minimum number of moves needed to rearrange the cubes.
In each of the following lines, output two integers and (1 \leq a, b \leq n; a \neq b), where is the column number from which you take a cube, and is the column number to which you place the cube.
Example 1
First, we will place the last column. Therefore, the only first move to rearrange the cubes in the minimum number of moves may be to move from the third column to the second, because otherwise we will not be able to place at the beginning of the third column if we do not move or do not move it to the second column.
First 3 states
After we have placed , we need to place and in their places in the third column, again the only way to do this is to first move to the first column, because otherwise we will not be able to place in the third column in the next move, and then place in its place.
Next 3 states
After this, we want to correctly place the second column, and for to be the first number, we first need to take , which we can only take in the last column. After we have placed , we only need to return to the second column to achieve the desired state of the cubes.
Final 3 states
( points): n = 4;
( points): n = 5;
( points): n = 6;
( points): n \le 10;
( points): n \le 100;
( points): no additional restrictions.
You can earn half the points for each block if you output the correct for each test in the block. You will also receive a quarter of the points if you output an incorrect , but the instructions are correct; in this case, k \le 10^6.
Note that to earn half the points, you need to output the correct and
either output nothing else; that is, output only , but no instructions;
or output all instructions completely, where all column numbers are from to . There are no additional requirements for them.
If you output, for example, only a few instructions, or too many instructions, or numbers that are not column numbers, etc., you will receive points.
Partial points are not awarded for the example from the statement, as it is scored at points.
The output for half points when n=3 could look like this:
8or like this:
8
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1The output for a quarter of the points when n=3 could look like this:
10
1 3
3 1
3 2
1 3
2 1
2 3
1 3
2 3
1 2
3 2If you output a number of instructions that does not equal , you will receive points:
8
1 3
3 1
3 2
1 3
2 1
2 3
1 3
2 3
1 2
3 2