Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Weird LCM Operations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer n, you construct an array a of n integers, where ai=i for all integers i in the range [1,n]. An operation on this array is defined as follows:

  • Select three distinct indices i, j, and k from the array, and let x=ai, y=aj, and z=ak.
  • Update the array as follows: ai=lcm(y,z), aj=lcm(x,z), and ak=lcm(x,y), where lcm represents the least common multiple.
Your task is to provide a possible sequence of operations, containing at most n6+5 operations such that after executing these operations, if you create a set containing the greatest common divisors (GCDs) of all subsequences with a size greater than 1, then all numbers from 1 to n should be present in this set.

After all the operations ai1018 should hold for all 1in.

We can show that an answer always exists.

Input

The first line contains one integer t (1t102) — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains an integer n (3n3104) — the length of the array.

It is guaranteed that the sum of n over all test cases does not exceed 3104.

Output

The first line should contain an integer k (0kn6+5) — where k is the number of operations.

The next k lines should contain the description of each operation i.e. 3 integers i, j and k, where 1i,j,kn and all must be distinct.

Example
Input
3
3
4
7
Output
1
1 2 3
1
1 3 4
3
3 5 7
5 6 7
2 3 4
Note

In the third test case, a=[1,2,3,4,5,6,7].

First operation:

i=3, j=5, k=7

x=3, y=5, z=7.

a=[1,2,lcm(y,z),4,lcm(x,z),6,lcm(x,y)] = [1,2,35,4,21,6,15].

Second operation:

i=5, j=6, k=7

x=21, y=6, z=15.

a=[1,2,35,4,lcm(y,z),lcm(x,z),lcm(x,y)] = [1,2,35,4,30,105,42].

Third operation:

i=2, j=3, k=4

x=2, y=35, z=4.

a=[1,lcm(y,z),lcm(x,z),lcm(x,y),30,105,42] = [1,140,4,70,30,105,42].

Subsequences whose GCD equal to i is as follows:

gcd

\gcd(a_3, a_4) = \gcd(4, 70) = 2

\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3

\gcd(a_2, a_3) = \gcd(140, 4) = 4

\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5

\gcd(a_5, a_7) = \gcd(30, 42) = 6

\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7