Friday

Time limit3sMemory limit512 MB

Summary

Given N up to 10^15, find the date of the N-th Friday strictly after December 21, 2012 under Gregorian leap year rules.

Level: Medium7 of 10
Topics: Math, Binary search, Implementation, Number theory
Solved: No attempts yet

Problem

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.

Input

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}$

Output

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.

Examples1

Example 1

Input

5
1
2
3
5
1234567890123

Expected output

December 28, 2012
January 4, 2013
January 11, 2013
January 25, 2013
October 8, 23660926551