문제

모그와 루날리티는 사이가 썩 좋지 않지만, 바닥에 타일을 깔고 색칠하는 일을 함께 맡게 되었다. 두 사람은 다음과 같이 역할을 나누기로 했다.

바닥은 무한한 크기의 좌표평면으로 이루어져 있다. 모그가 먼저 이 좌표평면에 개의 타일을 배치한다. 첫 번째 타일은 위치에 놓으며, 이후 새로운 타일을 놓을 때에는 다음 규칙을 반드시 따라야 한다.

• 어떤 위치 에 타일을 놓으려면, 그 위치의 상하좌우 인접 좌표인 , , , 중 적어도 한 곳에는 이미 타일이 놓여 있어야 한다.

모그가 모든 타일 배치를 마치면, 루날리티가 타일들을 색칠한다. 루날리티는 모그를 골탕 먹이기 위해 가능한 한 많은 종류의 색을 사용하려 한다. 각 타일은 하나의 색으로만 칠할 수 있다. 단, 모든 타일을 색칠한 뒤에는 다음 규칙을 만족해야 한다.

• 어떤 위치 에 있는 타일의 색이 라면, 그 타일의 상하좌우 인접 위치 중 적어도 한 곳에는 같은 색 로 칠해진 타일이 있어야 한다.

모그는 루날리티가 위 규칙을 지키면서 최적의 전략으로 색칠했을 때, 사용된 색의 개수가 정확히 개가 되도록 타일을 배치하고자 한다. 과 가 주어졌을 때, 모그가 타일을 어떻게 배치해야 하는지 구하여라. 이러한 배치가 불가능한 경우도 있을 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫째 줄에 양의 정수 가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 첫째 줄에 모그가 문제의 조건에 맞게 타일을 배치하는 것이 가능하다면 YES를, 불가능하다면 NO를 출력한다. 대소문자는 구분하지 않는다.

만약 가능하다면, 각 테스트 케이스의 둘째 줄부터 개의 줄에 걸쳐 배치할 타일의 좌표 를 공백으로 구분하여 출력한다. 이때 는 배치되는 순서대로 출력해야 하며, 각 타일은 배치되는 시점에 상하좌우 중 최소 한 곳에 이미 타일이 존재하는 위치여야 한다. 위치에는 처음부터 타일이 놓여있다고 생각한다.