Friday

December 21, 2012 was a Friday. You write down every Friday that comes after that day, in chronological order. The first entry of the list is the Friday right after December 21, 2012, and December 21 itself is not on the list.

To check the list you need the calendar rules exactly. A leap year is a year divisible by 4, except that a year divisible by 100 is not a leap year, and a year divisible by 400 is a leap year again. Assume this rule still holds in the very distant future.

The months in order, with the number of days each one has:

• January (31)
• February (28, or 29 in a leap year)
• March (31)
• April (30)
• May (31)
• June (30)
• July (31)
• August (31)
• September (30)
• October (31)
• November (30)
• December (31)

Write a program that finds the $N$-th date on the list.

The first line contains $T$, the number of test cases. Each of the next $T$ lines contains one integer $N$.

Constraints

• $1 \le T \le 50000$
• $1 \le N \le 10^{15}$

For each test case, print the $N$-th date on the list on its own line.

The format is MMM DD, YYYY. MMM is the full English month name with only the first letter capitalized (January, February, March, and so on). DD is the day of the month, written without a leading zero. YYYY is the year, which may have more than four digits. Put one space between the month name and the day, and a comma followed by one space after the day.