34035번 - 서로소 그래프 게임

문제

승민이와 찬영이는 서로소 그래프 게임을 하려고 한다. 이 게임은 간선이 없는 정점 $N$개로 시작하며, 두 사람은 번갈아 가며 다음과 같은 규칙으로 게임을 진행한다.

• 자신의 차례에는, 연결 요소에 속한 정점의 수가 서로소인 서로 다른 두 정점을 선택해 간선을 추가해야 한다.
• 간선을 추가할 수 있는 정점 쌍이 없다면, 해당 차례의 플레이어는 패배한다.

승민이가 먼저 시작하여 두 사람 모두 최선의 전략으로 게임을 진행할 때, 누가 승리하는지 판단하자.

입력

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

둘째 줄부터 $T$개의 줄에 걸쳐, 각 테스트 케이스에 대해 정점의 개수 $N$이 주어진다.

출력

각 테스트 케이스에 대해 승민이가 이긴다면 kang을, 찬영이가 이긴다면 chan을 한 줄에 하나씩 출력한다.

제한

• 1ドル \leq T \leq 100$
• 2ドル \leq N \leq 1,000円$

노트

두 정점 사이에 경로가 존재한다면, 두 정점은 연결되어 있다고 한다.

연결 요소는 내부에 속한 정점이 모두 연결된 부분 그래프이다.