GEOLYMP

We call a string T a subsequence of a string S if T can be obtained from S by deleting zero or more characters without changing the order of the remaining characters.

For example, from ABCDA, the strings ABC, AA, and AD are subsequences, while ACB and XYZ are not.

Let the target word be GEOLYMP.
Given an integer $K$ , construct any string $S$ of uppercase Latin letters such that:

S is at most 1000 characters long
The string "GEOLYMP" occurs as a subsequence of $S$ exactly $K$ times

It can be shown that a solution always exists under the constraints.

Constraints

$1 \leq K \leq 1 0^{9}$

Input Format

The first line contains an integer $T$ — the number of test cases.
Each of the next $T$ lines contains a single integer $K$ .

Output Format

For each test case $i$ ( $1 \leq i \leq T$ ), output Case #i: S, where S is any string of at most $1000$ uppercase letters having exactly $K$ subsequences equal to GEOLYMP.

Example

Input

1
5

Output

Case #1: GXEOLYMPMPP

Explanation

There are 5 subsequences (shown in bold) that produce GEOLYMP:

GXEOLYMPMPP
GXEOLYMPMPP
GXEOLYMPMPP
GXEOLYMPMPP
GXEOLYMPMPP