Alice

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
As a cryptologist, after working on numerous cryptographic protocols, Alice is now retired and living happily in Wonderland. However Alice is still obsessed with security, she even invented a new way to set passwords. Given a board of n rows and n columns with unitary size cells, Alice creates a password by drawing exactly n+1 lines with vertices of the integer points on the perimeter of the board.
One day Alice forgot her CodeChef password! She knew that she had set her password in the secure way. She remembers that no two lines were parallel, and that every cell of the board was cut by at least one of the lines. A cell is cut by a line when there exists a point strictly inside of the cell that belongs to the line.
Please help Alice finding one password satisfying the information that she remembered.
Input
The first line of the input contains one integer T the number of test cases.
Each test case is described by a line containing an integer n representing the size of the board.
Output
For each test case print n + 1 lines each of them containing four integers x_{1} y_{1} x_{2} y_{2} with x_{1} ≠ x_{2} and y_{1} ≠ y_{2}, representing a line that goes from (x_{1},y_{1}) to (x_{2},y_{2}).
If there are multiple passwords that satisfies the information, print any of them.
Constraints
 1 ≤ T ≤ 10
 1 ≤ n ≤ 10^{3}
Example
Input: 1 3 Output: 0 0 3 2 3 0 0 2 0 1 2 3 0 3 3 2
Explanation
One of the possible passwords is depicted in the above figure.
Every cell is cut by at least one line, for example the green cell is cut by the blue and purple lines, but not by the yellow one. The integer points on the perimeter of the board are drawn as small black circles.
Author:  alei 
Tester:  kingofnumbers 
Editorial  http://discuss.codechef.com/problems/ALICE 
Tags  alei, constructive, cook73, easymedium, gcd 
Date Added:  20072016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 