Đề bài

Trong một giờ học Toán, thầy giáo TrZit đưa ra một trò chơi trí tuệ cho hai bạn KOSHO và KIDO. Trên bảng là một số nguyên dương \(N\). Hai bạn sẽ lần lượt "gặm" dần các thừa số nguyên tố của \(N\) cho đến khi không còn gì để gặm nữa. Nghe thì đơn giản, nhưng có một quy tắc đổi lượt khá "quái" khiến người đi trước không phải lúc nào cũng nắm chắc phần thắng.

Luật chơi như sau:

Cho số nguyên dương \(N\) có phân tích thừa số nguyên tố:

\(N = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_r^{a_r}\)

trong đó \(p_1, p_2, \ldots, p_r\) là các số nguyên tố khác nhau, và \(a_1, a_2, \ldots, a_r \ge 1\).

KOSHO và KIDO luân phiên đi, KOSHO đi trước. Mỗi nước đi gồm 3 bước:

1. Chọn một số nguyên tố \(p_i\) (với \(a_i > 0\)) trong phân tích của \(N\).
2. Chọn một số nguyên dương \(k\) thỏa \(1 \le k \le a_i\).
3. Giảm \(a_i\) đi \(k\) đơn vị (tức là chia \(N\) cho \(p_i^k\)).

Quy tắc đổi lượt:

• Nếu \(k\) lẻ → người vừa đi nhường lượt cho đối thủ.
• Nếu \(k\) chẵn → người vừa đi được đi tiếp.

Trò chơi kết thúc khi \(N = 1\) (không còn thừa số nguyên tố nào để chọn). Người đến lượt mà không thể đi được thì thua.

Lưu ý: ngay cả khi \(N = 1\) ngay từ đầu (\(r = 0\), không có thừa số nguyên tố nào), KOSHO — người đi trước — sẽ là người đầu tiên rơi vào tình huống "đến lượt mà không đi được", nên KOSHO thua ngay lập tức và KIDO thắng tuyệt đối, dù chưa có nước đi nào diễn ra.

Với mỗi \(N\), hãy xác định ai là người thắng cuộc khi cả hai chơi tối ưu.

Input

• Dòng 1: một số nguyên \(T\) (\(1 \le T \le 10^6\)) — số lượng truy vấn.
• \(T\) dòng tiếp theo: mỗi dòng một số nguyên \(N\) (\(1 \le N \le 10^6\)).

Output

In ra \(T\) dòng, mỗi dòng là KOSHO hoặc KIDO.

Giới hạn

• Subtask 1 (20%): \(1 \le T \le 10,\ 1 \le N \le 10^2\)
• Subtask 2 (20%): \(1 \le T \le 100,\ 1 \le N \le 10^3\)
• Subtask 3 (20%): \(1 \le T \le 10^4,\ 1 \le N \le 10^4\)
• Subtask 4 (20%): \(1 \le T \le 10^5,\ 1 \le N \le 10^5\)
• Subtask 5 (20%): \(1 \le T \le 10^6,\ 1 \le N \le 10^6\)

Ví dụ

Input:

5
1
4
8
30
360

Output:

KIDO
KIDO
KOSHO
KOSHO
KIDO

Giải thích:

• \(N = 1\): không có thừa số nguyên tố nào (\(r = 0\)), nên đến lượt KOSHO nhưng không có nước đi hợp lệ ⟹ KIDO thắng ngay từ đầu, đúng như lưu ý ở trên.
• \(N = 8 = 2^3\): KOSHO chọn \(p = 2\), \(k = 3\) (lẻ). Số mũ giảm từ 3 về 0, \(N\) trở thành 1, và vì \(k\) lẻ nên lượt được nhường cho KIDO. Đến lượt KIDO, \(N = 1\), KIDO không có nước đi hợp lệ ⟹ KOSHO thắng.