룩 백

그림을… 더 잘 그리고 싶으니까.

— 쿄모토, 「룩 백」

이 문제는 인터랙티브 문제입니다.

$2N \times 2N$ 크기의 체스판 위에 룩이 $N(N = {\color{ForestGreen}{100}})$개 올려져 있다. 각 칸에는 최대 한 개의 룩만 있을 수 있다. 체스판의 $i$행 $j$열$(1 \leq i, j \leq 2N)$의 칸은 $(i, j)$와 같이 나타낸다. 하지만 당신은 체스판을 볼 수 없다.

룩은 같은 행 또는 같은 열에 있는 다른 룩을 공격할 수 있다. 단, 룩은 다른 룩을 넘어 공격할 수 없다. 즉, 같은 행 또는 같은 열에 있는 두 룩 사이에 다른 룩이 존재하지 않을 때에만 두 룩은 서로 공격 가능하다.

당신의 목표는 다음과 같은 질문을 최대 $3N$번 하여 서로 공격 가능한 룩 쌍의 수를 알아내는 것이다. 여기서 같은 두 룩으로 이루어진 쌍은 순서와 관계없이 한 번만 센다.

• $?$ $x_1\, y_1\, x_2\, y_2$: 체스판에서 행 번호가 이상 이하이고, 열 번호가 이상 이하인 칸들로 이루어진 직사각형 영역 안에 존재하는 룩의 개수를 반환한다.

당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.

입력은 하나 이상의 테스트 케이스로 이루어져 있다. 먼저, 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스에 대해서 아래와 같이 상호작용해야 한다. $(1 \leq T \leq 100)$

테스트 케이스의 첫 번째 줄에 정수 $N$이 주어진다. $(N = 100)$

당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.

• C : fflush(stdout)
• C++ : std::cout.flush()
• Python : sys.stdout.flush()
• Java : System.out.flush()
• 그 외의 언어는 각 언어의 Documentation을 참고한다.