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 alined with each other.

Two stones are called alined 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 containg 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
1 1

2 4

3 2

4 5

3 2
5 3