JUNIOR_G's closest friend JHA_G is very kind and helping person. He invites every girl to his HAWELI ("AAO KABHI HAWELI PE"), so that he can help them :) . As he is also good in problem solving so to be his guest girls have to solve a problem to open the door.

Door contains a square grid of size n×n (3 < n < 31) and have n stones. Place those stones in such a way that no two stones should be aligned with each other.

Two stones are called aligned if:

i) they share common row or column.

ii) or they share common diagonal i.e. a straight line going through 'a' and 'b' is a diagonal for all smallest square between them.

"CODING IS FUN ENJOY IT" :)

Input

First line contain an integer T (0 < T < 10001). Each test case contain an integer n (3 < n < 31).

Output

For each test case output n lines containing row number and column number (1 based indexing and sorted according to row number (increasing order)).

Example:

Input:
1
5
Output:
1 1
2 4
3 2
4 5
5 3