1차원 돌 게임 2

이 문제는 1차원 돌 게임 1과 굵은 글씨로 적힌 부분만 다릅니다.

동우와 재우는 $1\times n$ 모양의 직선형 격자판에서 처음에 각 칸에 돌을 한 개씩 올려 둔 상태로 게임을 진행하려 한다.

게임은 동우부터 시작해 턴을 번갈아 가며 돌을 가져간다. 즉, 동우는 홀수 번째 턴에, 재우는 짝수 번째 턴에 진행한다.

• 첫 번째 턴에는 $1$개의 칸을 골라 그곳에 놓인 돌을 가져간다.
• 두 번째 턴부터는 직전 턴에 상대방이 가져간 돌의 개수가 $x$개라면, $1$ 이상 $x+1$ 이하의 정수 $y$를 하나 골라서, 돌이 놓인 연속한 $y$개의 칸을 골라 그 칸들에 놓인 모든 돌을 가져간다.
• 돌을 가져갈 때마다 가져간 칸(들)을 기준으로 남은 돌이 두 부분으로 나뉘면, 돌의 개수가 더 적은 부분에 놓인 돌을 모두 버린다. 두 부분의 돌 개수가 같다면 한 부분을 골라 그 부분의 돌을 모두 버린다. 두 부분으로 나뉘지 않고 한 부분만 남으면 버리지 않는다.
• 자신의 턴에 조건에 맞게 돌을 가져가지 못하면 그 사람이 패배하고, 상대방이 승리한다.

두 사람이 승리하기 위해 최선의 플레이를 한다면 누가 이기는지 출력하시오.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T \le 10^6)$

각 테스트 케이스마다 한 줄에 초기 돌의 개수 $n$이 하나씩 주어진다. $(1\le n\le 10^{18})$

같은 $n$은 여러 번 주어지지 않는다.

각 테스트 케이스에 대해 동우가 이기면 kidw0124를, 재우가 이기면 eoaud0108을 한 줄에 하나씩 출력한다.