JHAGIRLS - AAO KABHI HAWELI PE :P

no tags 

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

hide comments
Tapasweni Pathak: 2017-04-05 03:44:22

Last edit: 2017-04-05 06:22:37
Ankush : 2017-03-23 12:41:46

Aa gaye Haweli pe :P N-queens problem, lol

deadbrain: 2017-03-19 19:57:58

The test cases are weak... A wrong AC solution gave this output on n=4 :
1 3
2 0
3 4
4 0

Kindly mend the test cases asap.

Last edit: 2017-03-19 20:01:49
abis: 2017-03-15 13:40:02

print any solution

rajeev_899: 2017-03-15 08:01:30

@ problem setter ...can we print any solution out of multiple solutions to the problem

Praveen Gajulapalli: 2017-03-13 14:21:07

The problem has multiple solutions. Print any one of them.

useandthrowone: 2017-03-11 13:46:48

how can i avoid TLE?

[Rampage] Blue.Mary: 2017-03-11 13:10:15

This is surely a tutorial problem, a much harder version already exists in SPOJ: http://www.spoj.com/problems/NQUEEN/

Priyanjit Dey: 2017-03-11 12:42:28

Looks like there are more than one solution possible. Is it okay to print any one of them?


Added by:junior_g
Date:2017-03-11
Time limit:0.141s-0.583s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All