삼각 N-Queen

한 변에 N칸이 있는 삼각형 모양의 체스판이 있다. 위에서부터 행 번호를 1부터 N까지 붙이고, i번째 행에는 왼쪽부터 열 번호 1부터 i까지 붙은 i개의 칸이 있다.

퀸은 자신이 놓인 칸을 지나는 세 방향의 줄, 즉 삼각형의 세 변과 각각 평행한 줄에 있는 모든 칸을 공격한다. 이 좌표계에서는 두 퀸이 같은 행에 있거나, 같은 열에 있거나, 행 번호와 열 번호의 차가 같으면 서로 공격한다.

삼각 N-Queen 문제는 한 변에 N칸이 있는 삼각형 체스판에 서로 공격하지 않도록 가능한 한 많은 퀸을 배치하는 것이다. 한 변의 칸 수가 N이면 항상 floor((2*N+1)/3)개의 퀸을 서로 공격하지 않게 배치할 수 있다.

N이 주어졌을 때, 서로 공격하지 않는 퀸의 최대 개수와 그 배치를 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 C(1 <= C <= 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며 정수 N(1 <= N <= 1000)을 포함한다.

각 테스트 케이스마다 첫 줄에 놓을 수 있는 퀸의 최대 개수를 출력한다. 이어지는 N개 이하의 줄에는 실제로 놓는 퀸들의 위치를 한 줄에 하나씩 출력한다.

위치는 행 번호와 열 번호를 공백으로 구분해 출력한다. 제일 윗줄의 행 번호는 1이고, 각 행의 가장 왼쪽 칸의 열 번호는 1이다. 가능한 배치가 여러 가지이면 그중 아무 배치나 출력해도 된다.