도미노

비 오는 어느 날 Lech와 Grzegorz는 도미노를 가지고 놀며 시간을 보내고 있었다. 이들의 도미노 세트는 보통 것보다 조금 크다. 세트에는 $\frac{n(n + 1)}{2}$개의 조각이 있고, 각 조각은 정수가 하나씩 적힌 두 반쪽으로 이루어져 있다. 조각은 (1 1), (1 2), ..., (1 n), (2 2), (2 3), ..., (n n) 순으로 번호가 매겨져 있다.

둘은 정해진 규칙대로 노는 것이 금방 지루해져서 더 어려운 것을 생각해 냈다. Grzegorz의 제안은 이렇다. 모든 조각을 붙여서, 같은 정수가 적힌 반쪽들이 하나의 연결된 영역을 이루게 한다. 모든 1은 한 곳에, 모든 2는 다른 한 곳에 모이는 식이다. 조각을 놓기 시작했지만 금방 매우 어려워졌다. Lech가 악마처럼 웃으며 말했다. "좋은 생각이 있어. 이 과제를 학생들에게 맡기자!"

조각은 단위 정사각형으로 나뉜 큰 보드 위에 놓아야 한다. 각 도미노는 정확히 단위 정사각형 두 칸을 차지하며, 각 칸에는 숫자가 하나씩 있다. 가로나 세로로 놓을 수 있다. 조각끼리 겹칠 수 없다. 두 단위 정사각형이 변을 공유하면 연결된 것으로 본다.

첫 줄에 테스트 케이스의 수 $z$ ($1 \leq z \leq 50$)가 주어진다. 각 테스트 케이스는 정수 $n$ ($1 \leq n \leq 1000$) 하나가 적힌 한 줄로 주어진다.

각 테스트 케이스마다 해가 없으면 impossible을 한 줄에 출력한다. 해가 있으면 $\frac{n(n + 1)}{2}$개의 줄에 조각의 위치를 출력한다. 첫 줄은 (1 1) 조각, 그다음은 (1 2) 조각 순서이며, 마지막 줄은 (n n) 조각이다. 각 위치는 정수 네 개 $x_1, y_1, x_2, y_2$ ($0 \leq x_1, x_2, y_1, y_2 \leq 10\,000\,000$)로 나타낸다. $x_1, y_1$은 숫자가 작거나 같은 쪽 반쪽의 좌표이고, $x_2, y_2$는 숫자가 크거나 같은 쪽 반쪽의 좌표이다.