See Problem N for PDF statements.

As the builder employed by NIO, you need to build more walls for him. Now you have a number of bricks of height but with different lengths. More precisely, you have bricks of length , bricks of length , ..., two bricks of length , and one brick of length . The width of the bricks is negligible. You need to build a wall with these bricks whose shape must be strictly rectangular. When building the wall, you must keep the height of the bricks at , which means you cannot rotate them.

Of course, you can definitely build a wall with a height of and a large length, but it is not a beautiful wall. In NIO's opinion, a beautiful wall should have the minimum possible circumference. Please tell him the minimum circumference of the wall, and how to build it.

输入描述:

The first line contains an integer  (), indicating the number of test cases.

Each test case contains an integer  () in a single line. It is guaranteed that the sum of  over all test cases won't exceed .

输出描述:

For each test case, output an integer in a single line, indicating the minimum circumference of the wall. Then in the next  lines, each line contains four integers , indicating that the coordinate of the lower left of the brick is , and the upper right is .

You can consider the wall as a rectangular in the Cartesian coordinate system, where the -axis represents the length and the -axis represents the height. The lower left of the wall must be located at . If there are multiple solutions, output any.

4
1
2
3
4

4
0 0 1 1
8
0 1 1 2
1 1 2 2
0 0 2 1
14
2 1 3 2
3 1 4 2
4 1 5 2
3 0 5 1
0 1 2 2
0 0 3 1
18
4 0 5 1
2 3 3 4
3 3 4 4
4 3 5 4
3 1 5 2
3 2 5 3
0 3 2 4
0 1 3 2
0 2 3 3
0 0 4 1

A possible solution for the third test case in the sample: