EdoceRahs

Time Limit: 3 Seconds    Memory Limit: 65536 KB

“Edoce” and “Rahs” are twin sisters and they are very close to each other as often their friends call them “edocerahs”. They have a special ability! They can manipulate numbers in their minds. Although they are twins, but they have different approaches and preferences in order to manipulate numbers. Edoce prefers odd numbers rather than even numbers and Rahs likes even numbers more than odd numbers. Their hobby is to choose any random number N and write down the numbers 1 through N on the paper. Say for N = 12 they write 123456789101112. Edoce starts with eliminating all the digits in odd indices to create another sequence of numbers and then eliminate all the digits in even indices and so on. When only one digit remains, that is going to be Nth Edoce’s number. Rahs also does the same, but she starts with eliminating even indices first and then odd indices and so on (indices start from 0).
For N = 12, Edoce’s first sequence would be: 13579012. Then by eliminating even indices: 3702, then odd indices: 30, and then by removing the digit 3, the remaining digit would be 0, so the 12th Edoce’s number is 0.
Rahs, on the other hand, first would have: 2468111. Then by eliminating odd indexes: 2611, then even indexes: 61, and finally removing 1 and the remaining digit would be 6, so the 12th Rahs’ number is 6.

Write a program to compute Nth Edoce’s number and Rahs’ number.

Input

The input contains several test cases.
In the first line of input comes T (0 < T ≤ 100001), the number of test cases.
Each line of the following T lines is a case, containing the integer N(0 < N < 100000).

Output

For each case, write “Edoce:X, Rahs:Y” in a line which X is Nth Edoce’s number and Y is Nth Rahs’ number.

Sample Input

2
4
12

Sample Output

Edoce:3, Rahs:2
Edoce:0, Rahs:6
Submit

Source: 12th Iran Nationwide Internet Contest - Final