배열을 정렬해 본 적이 있는가?

이제부터 여러분은 교준이와 간단한 게임을 한다.

교준이는 마음속으로 1부터 N까지의 자연수 N개로 이루어진 수열 A를 생각한다. 교준이는 여러분에게 자연수 N만 알려준다. 여러분은 아직 수열 A를 정확히 알지 못한다.

여러분은 교준이 마음속에 있는 수열 A를 알아내기 위해 교준이에게 다음과 같은 질문을 할 수 있다.

• "수열 A의 a번째 수와 b번째 수 중 어느 쪽이 더 큰가?" (1 ≤ a < b ≤ N)

최소한의 질문으로 수열 A를 정확하게 알아내는 것이 이 게임의 목표이다. 교준이와 이 게임을 진행하는 프로그램을 작성하시오.

Sample Grader는 다음과 같은 정보를 표준 입력으로 읽는다. 여러분은 어떠한 입력도 받으면 안 된다.

첫 번째 줄에 교준이와 할 게임의 총 판 수와 교준이가 생각한 수열 A의 길이를 나타내는 자연수 T, N이 공백을 사이에 두고 주어진다.

두 번째 줄부터 T개의 줄에 걸쳐, 수열 A를 나타내는 N개의 자연수가 공백을 사이에 두고 주어진다.

Sample Grader는 다음과 같은 정보를 표준 출력으로 출력한다. 여러분은 어떠한 출력도 하면 안 된다.

여러분이 T판의 게임에서 모두 수열 A를 정확하게 알아낸 경우 Sample Grader는 "Accept. Max Questions = %d"의 형태로 출력한다. 이때 "%d"는 여러분이 게임 한 판에서 함수 compare를 가장 많이 호출한 횟수를 나타내는 정수이다.

Sample Grader가 "틀렸습니다"라고 판정한 경우 Sample Grader는 "Wrong Answer [4]"와 같은 형태로 출력한다.

• 1 ≤ T ≤ 5 × 10^4
• 1 ≤ N ≤ 7
• 1 ≤ A_i ≤ N (1 ≤ i ≤ N)
• A_i ≠ A_j (1 ≤ i < j ≤ N)