Description

For simplified calculations, astronomers use Julian Day (JD) to express time. The Julian Day is defined as the number of days that have elapsed since noon (12:00) on January 1, 4713 BC, up to a given moment, with fractions of a day expressed as decimals. By using this astronomical calendar, every moment can be uniformly mapped onto a number line, making it very convenient to calculate time differences.

Now, given a Julian Day without a fractional part, please help calculate the corresponding Gregorian calendar date (which must be noon on a certain day).

Our current calendar is the Gregorian calendar, which was introduced by Pope Gregory XIII in 1582 AD as a modification of the Julian calendar (note: the Julian calendar is not directly related to Julian Day). Specifically, the current Gregorian calendar dates are calculated according to the following rules:

1. On or after October 15, 1582 AD: The Gregorian calendar applies. The months have the following lengths: January (31 days), February (28 or 29 days), March (31 days), April (30 days), May (31 days), June (30 days), July (31 days), August (31 days), September (30 days), October (31 days), November (30 days), December (31 days). A leap year has 29 days in February, while a common year has 28 days. A year is a leap year if it is divisible by 400, or if it is divisible by 4 but not by 100.

2. Between October 5, 1582 AD, and October 14, 1582 AD (inclusive): These dates do not exist. They were deleted, so October 4 was followed by October 15 in that year.

3. On or before October 4, 1582 AD: The Julian calendar applies. The months have the same lengths as in the Gregorian calendar, but a year is a leap year if it is divisible by 4.

4. Although the Julian calendar was introduced in 45 BC and underwent several adjustments in its early stages, today it is customary to retroactively apply the final rules of the Julian calendar to all dates before October 4, 1582.

Note that the year 0 AD does not exist. That is, the year following 1 BC is 1 AD. Therefore, years such as 1 BC, 5 BC, 9 BC, 13 BC, etc., should be considered leap years.

Input Format

The first line contains an integer Q, indicating the number of queries.

The next Q lines each contain a non-negative integer ri, representing a Julian Day.

Output Format

For each Julian Day ri, output a line containing the date string s_i. There should be Q lines in total.

The format of s_i is as follows:

1. If the year is AD (Anno Domini), the output format is Day Month Year. The day (Day), month (Month), and year (Year) should not have leading zeros, and they should be separated by a single space.

   For example: Noon on November 7, 2020 AD should be output as 7 11 2020.

2. If the year is BC (Before Christ), the output format is Day Month Year BC. The year (Year) should be output as its numerical value, and the rest is the same as for AD years. For example: Noon on February 1, 841 BC should be output as 1 2 841 BC.

3
10
100
1000

11 1 4713 BC
10 4 4713 BC
27 9 4711 BC

3
2000000
3000000
4000000

14 9 763
15 8 3501
12 7 6239

Source

CSP2020-S1

(Note: This appears to be an abbreviated reference code, possibly indicating a standardized exam or document identifier. Without additional context, the translation maintains the original alphanumeric format which is commonly used for exam codes in both languages.)