Triangular N-Queen

There is a triangular chessboard with N cells on each side. Number the rows from top to bottom starting at 1. Row i has i cells, numbered from left to right starting at 1.

A queen attacks every cell on each of the three lines through its cell that are parallel to the three sides of the triangle. In these coordinates, two queens attack each other if they share a row, share a column, or have the same value of row minus column.

The triangular N-Queen problem asks you to place as many queens as possible on a triangular board of side length N so that no two queens attack each other. For every N, it is always possible to place floor((2*N+1)/3) non-attacking queens.

Given N, write a program that prints the maximum number of non-attacking queens and one placement achieving it.

The first line contains the number of test cases C (1 <= C <= 1000). Each test case consists of one line containing an integer N (1 <= N <= 1000).

For each test case, print the maximum number of queens that can be placed on the first line. Then print the positions of the queens you place, one per line.

Print each position as a row number and a column number separated by a space. The top row has row number 1, and the leftmost cell in each row has column number 1. If several placements are possible, you may print any one of them.