$A$ 의 배수

시간 제한2초메모리 제한1024 MB

요약

1부터 N까지의 정수가 적힌 칠판에서 두 사람이 번갈아 수를 지우되, A의 배수를 지운 직후에는 그 몫 x/A를 지울 수 없다. 최선의 플레이에서 승자를 가린다.

난이도: 어려움10점 중 8점
유형: 게임 이론, 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

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를 한 줄에 하나씩 출력하라.

예제1

예제 1
입력
```
3
2 2
4 2
3 3
```
예상 출력
```
O
I
O
```