34124번 - $A$의 배수

문제

ohwphil과 iktk가 2인용 게임인 $A$의 배수 게임을 하고 있다.

칠판에 1ドル$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 적혀 있다. 각 사람은 자신의 턴에 번갈아 가며 칠판에 적힌 정수 하나를 지운다. 단, 상대방이 가장 최근에 지운 수 $x$가 $A$의 배수인 경우 $\frac{x}{A}$는 지울 수 없다. 지워진 수가 없다면 아무 수나 지울 수 있다. 자신의 차례에 더 이상 지울 수가 없는 사람이 패배하고 상대방이 승리하게 된다.

$N$과 $A$가 주어질 때마다 두 사람이 최선을 다해서 플레이할 때 ohwphil과 iktk 중 누가 승리하는지 결정해 보자. 게임은 ohwphil부터 시작한다.

입력

첫째 줄에 테스트 케이스의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 10^6$)

둘째 줄부터 $Q$개의 줄에 걸쳐 양의 정수 $N$과 $A$가 공백으로 구분되어 주어진다. (2ドル \leq A \leq N \leq 10^9$)

출력

주어진 테스트 케이스마다 ohwphil이 게임에서 승리하면 O, iktk가 게임에서 승리하면 I를 한 줄에 하나씩 출력하라.

제한

힌트