잘못된 해시 학생들

해시 테이블은 컴퓨터 과학에서 널리 쓰이는 자료 구조로, 서로 다른 항목을 비교적 작은 배열에 저장할 수 있게 해 준다. 해시 테이블에는 여러 구현 방식이 있고, 오버플로와 충돌을 처리하는 방법도 다양하다. 그중 하나는 개방 주소법과 이차 탐사(quadratic probe)를 사용하는 해싱이다.

동작 방식은 다음과 같다. 고정된 정수 상수 $\alpha$에 대해 해시 테이블 $T$의 길이가 $n$이고 셀 $T[0]$, $T[1]$, $T[2]$, ..., $T[n-1]$로 이루어져 있다고 하자. 객체를 저장하려면 먼저 초기 해시 함수를 적용해 초기 키 $k_1$을 계산하는데, 이는 0과 $n-1$ 사이의 인덱스일 뿐이다. $T$의 $k_1$ 위치에 객체를 저장하려고 시도한다. $T[k_1]$이 이미 사용 중이면 인덱스 $k_2 = k_1+\alpha\cdot 1^2 \mod n$인 다른 위치를 시도한다. $T[k_2]$도 이미 사용 중이면 $k_i = k_1+\alpha\cdot (i-1)^2 \mod n \text{ for } i= 3,4,5, \dots,$인 위치에서 탐사를 계속하고, 배열 $T$에서 처음으로 비어 있는 위치를 찾을 때까지 이어진다. $n$번 탐사한 뒤에도 $T$에서 빈 셀을 찾지 못하면 포기하고 예외를 발생시킨다. 이런 저장 방식은 초기 키 $k_1$을 계산하는 해시 함수가 정수 구간 $[\![ 0,n-1]\!]$에 값을 균일하게 분포시키고, 저장할 객체의 수 $m$이 $n$보다 조금 작을 때 잘 동작한다고 여겨진다.

Amaretto 교수 수업의 2학년 학생들은 해시 테이블을 구현하라는 과제를 받았다. 그런데 단 한 명도 제대로 해내지 못했다. Mayor 교수의 1학년 수업에서는 결코 일어나지 않았을 끔찍한 상황이다. Amaretto 교수가 학생들이 짠 코드를 이해하는 데는 오랜 시간이 걸렸다. 학생들의 첫 번째 실수는 복잡하게 고른 초기 해시 함수에 버그가 있어 항상 같은 값 $k_1$을 반환한다는 점이었다. 두 번째 실수는 모두 올바른 공식 대신 $k_i = k_1+\alpha\cdot {k_{i-1}}^2 \mod n$이라는 공식을 코딩했다는 점이었다.

그래도 Amaretto 교수는 잘못된 해시를 짠 학생들이 엉망으로 구현한 이 고장 난 해시 테이블이 얼마나 쓸 만한지 궁금해한다.

입력 파일은 여러 테스트 케이스로 이루어진다. 입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $c$가 하나 주어진다. 각 테스트 케이스는 정수 $n$, $k_1$, $\alpha$가 단일 공백으로 구분되어 한 줄에 주어지며, $n$ ($2\le n \le 200000000$)은 해시 테이블의 크기, $k_1$ ($0\le k_1 \le n-1$)은 잘못 코딩된 초기 해시 함수가 항상 반환하는 값, $\alpha$ ($1\le \alpha \le n-1$이고 $\alpha \le 100$)는 버그가 있는 이차 탐사에 사용되는 계수이다.

입력의 각 테스트 케이스마다 해시 테이블에서 값을 할당할 수 있는 셀의 수를 나타내는 정수 하나를 한 줄에 출력한다.