Person in Charge

Problem Description

For the convenience of calculation, astronomers use the Julian day to express time. The so-called Julian day is defined as the number of days elapsed from 12:00 noon on January 1, 4713 BC to a certain moment thereafter; fractions of a day are expressed as decimals. Using this astronomical calendar, every moment is uniformly mapped to the number axis, making it convenient to calculate the difference between them.

Now, given a Julian day without a decimal part, please help calculate the Gregorian calendar date corresponding to this Julian day (which must be 12:00 noon on a certain day).

The Gregorian calendar we currently use was modified by Pope Gregory XIII in 1582 based on the original Julian calendar (note: the Julian calendar has no direct relation to the Julian day). Specifically, the current Gregorian calendar date is calculated according to the following rules:

1. On and after October 15, 1582 AD: The Gregorian calendar applies. Each year has 31 days in January, 28 or 29 days in February, 31 days in March, 30 days in April, 31 days in May, 30 days in June, 31 days in July, 31 days in August, 30 days in September, 31 days in October, 30 days in November, and 31 days in December. Among them, February has 29 days in a leap year and 28 days in a common year. A year is a leap year if it is a multiple of 400, or if it is a multiple of 4 but not a multiple of 100.
2. From October 5, 1582 AD (inclusive) to October 14, 1582 AD (inclusive): These dates do not exist; they were deleted, and October 4 of that year was followed by October 15.
3. On and before October 4, 1582 AD: The Julian calendar applies. The number of days in each month is the same as in the Gregorian calendar, but a year is a leap year if it is a multiple of 4.
4. Although the Julian calendar was not implemented until 45 BC and underwent several adjustments in its early days, today humans are accustomed to retroactively applying the final rules of the Julian calendar to all times before October 4, 1582. Note that the year 0 AD does not exist—that is, the year following 1 BC is 1 AD. Therefore, the years 1 BC, 5 BC, 9 BC, 13 BC, and so on should be regarded as leap years.

Input Format

The first line contains an integer $Q$, representing the number of queries.
The next $Q$ lines each contain a non-negative integer $r_i$, representing a Julian day.

Output Format

For each Julian day $r_i$, output a line of string $s_i$ representing the date. There are a total of $Q$ lines. The format of $s_i$ is as follows:

1. If the year is AD, the output format is Day Month Year. Here, Day, Month, and Year have no leading zeros and are separated by a single space. For example: 12:00 noon on November 7, 2020 AD is output as 7 11 2020.
2. If the year is BC, the output format is Day Month Year BC. Here, Year is the numerical value of the year, and the rest are the same as in the AD format. For example: 12:00 noon on February 1, 841 BC is output as 1 2 841 BC.

Sample 1

See julian/julian1.in and julian/julian1.ans in the contestant's directory.

Sample 2

See julian/julian2.in and julian/julian2.ans in the contestant's directory.

Sample 3

See julian/julian3.in and julian/julian3.ans in the contestant's directory.

Data Range