[Solution] Birthday solution codeforces

Birthday solution codeforces – Vitaly gave Maxim 𝑛n numbers 1,2,,𝑛1,2,…,n for his 1616-th birthday. Maxim was tired of playing board games during the celebration, so he decided to play with these numbers. In one step Maxim can choose two numbers 𝑥x and 𝑦y from the numbers he has, throw them away, and add two numbers 𝑥+𝑦x+y and |𝑥𝑦||x−y| instead. He wants all his numbers to be equal after several steps and the sum of the numbers to be minimal.

Help Maxim to find a solution. Maxim’s friends don’t want to wait long, so the number of steps in the solution should not exceed 20𝑛20n.

Birthday solution codeforces

The first line contains a single integer 𝑡t (1𝑡250001≤t≤25000) — the number of test cases.

Each test case contains a single integer 𝑛n (2𝑛51042≤n≤5⋅104) — the number of integers given to Maxim.

It is guaranteed that the total sum of 𝑛n doesn’t exceed 51045⋅104.


For each test case print 1−1 if it’s impossible to make all numbers equal.

Otherwise print a single integer 𝑠s (0𝑠20𝑛0≤s≤20n) — the number of steps. Then print 𝑠s lines. The 𝑖i-th line must contain two integers 𝑥𝑖xi and 𝑦𝑖yi — numbers that Maxim chooses on the 𝑖i-th step. The numbers must become equal after all operations.

Don’t forget that you not only need to make all numbers equal, but also minimize their sum.

Birthday solution codeforces


output Birthday solution codeforces

1 3
2 2
4 0

Leave a Comment