Zach and Cody are playing a game. There are initially n chips on a table. Zach starts the game making the first move. In each turn one has to choose a move from a set of moves. The set of moves consists of all the moves of removing p^k chips from the table, where p is any prime and k is any non negative integer. The winner is the one who takes the last chip. Can you decide who will win the game, assuming both the players follow a perfect strategy? If Zach wins, what will be the smallest possible number that he can remove in his first move?
Input An integer T, denoting the number of test cases (1<= T<= 100000). Each test case contains one integer n, the number of chips on the table.
1 <= n <= 10^5 1 <= T <= 100000
Print â€œZachâ€ (followed by smallest possible number that he can remove in his first move) if Zach wins or â€œCodyâ€ if Cody wins. Print the output for each test case on a new line (without quotes).