## Chips

Time Limit: 5 sec
Memory Limit: 64 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

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.

Constraints

1 <= n <= 10^5

1 <= T <= 100000

Output

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).

Example

Input:

3

1

5

6

Output:

Zach 1

Zach 5

Cody

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED