A friend of mine has lost his cellular phone, and so his calendar.

Help him find the easter festival date of the year Y. (1584 < Y < 16000,)

Input

N lines.

Each line of the input contains Y. The last line ends with EOF.

Output

Output consist of exactly N lines.

The format of one line of output is: "Y: D M"

where D, M = day and month name in the Gregorian calendar.

Example

Input:
2012

Output:
2012: 8 April