Under construction

Still being built. Things may change

Judicious cuts (Easy)

Time limit1sMemory limit1024 MB

Summary
Given n, output lines y = mx + b (at most 1000 lines, coefficients within 10000) that split the plane into exactly n regions.
Level

Medium5 of 10

Topics
Math, Greedy, Geometry
Solved
No attempts yet

Problem

"Draw seven red lines, all of them strictly perpendicular to each other, some of them with green ink and some of them with transparent ink. Also, one of them should be in the form of a kitten." (The Expert)

Don't worry, your task is much simpler. We stay in the two-dimensional plane.

A straight line cuts the plane into two regions. With two such lines you can cut the plane into three regions (if the lines are parallel) or into four regions (if the lines intersect).

The figure below shows three lines arranged to cut the plane into 7, 6, and 6 regions, respectively.

We want to divide the plane into rr regions. Tell us how to draw the lines.

You may output any set of lines that divides the plane into exactly rr regions and follows the output format below.

Input

The first line of the input contains an integer tt (t≤1000t \le 1000), the number of test cases. Each test case is preceded by a blank line.

Each test case is a single line containing one integer nn (1≤n≤10001 \le n \le 1000), the desired number of regions.

Output

The output for each test case starts with a line containing a single integer ℓ\ell, the number of lines you want to draw. Then output ℓ\ell lines, each describing one line in the plane. Each line is given by two space-separated integers mm and bb, representing the equation y=mx+by = mx + b. (Vertical lines are not allowed. Obviously, you do not need to draw them.)

For each test case you can use at most 1000 lines. All slopes mm and y-intercepts bb must be between −10000-10000 and 1000010000, inclusive. Solutions are guaranteed to exist for all valid test cases.

Hint

For n=2n = 2, a single line divides the plane into 2 regions. For n=4n = 4, two intersecting lines divide the plane into four quadrants. The solution shown for the third case is not optimal, so it would not be accepted in the hard subproblem.

Examples1

  1. Example 1

    Input
    3
    
    2
    
    4
    
    35
    
    Expected output
    1
    0 5
    2
    2 0
    -2 4
    10
    2 0
    1 1
    0 1
    0 2
    0 3
    0 4
    0 5
    0 6
    -1 3
    -2 4