Description

To simplify 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 UTC) on January 1, 4713 BC, with fractions of a day expressed as decimals. By using this astronomical calendar, each moment is uniformly mapped onto a number line, making it convenient to calculate time differences.

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

Our current civil 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 days: January (31), February (28 or 29), March (31), April (30), May (31), June (30), July (31), August (31), September (30), October (31), November (30), December (31). Leap years have 29 days in February, while common years have 28. A year is a leap year if it is divisible by 400 or 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 skipped, with October 4 followed by October 15.

3. On or before October 4, 1582 AD: The Julian calendar applies. The months have the same number of days 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 finalized Julian calendar rules to all dates before October 4, 1582.

Note: The year 0 AD does not exist. The year following 1 BC is 1 AD. Thus, years like 1 BC, 5 BC, 9 BC, 13 BC, etc., should be considered leap years.

Input Format

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

Each of the next ( Q ) lines contains a non-negative integer ( r_i ), representing a Julian Day.

Output Format

For each Julian Day ( r_i ), output a date string ( s_i ) in one line. There should be ( Q ) lines in total.

The format of ( s_i ) is as follows:

1. For years AD (Anno Domini): The format is Day Month Year. The day, month, and year are printed without leading zeros, separated by single spaces.
   Example: For noon on November 7, 2020 AD, the output is 7 11 2020.

2. For years BC (Before Christ): The format is Day Month Year BC. The year is printed as its absolute value, while the rest follows the same format as AD.
   Example: For noon on February 1, 841 BC, the output is 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: The original text "CSP2020-S1" appears to be an abbreviated code or identifier, possibly referring to an exam, certification, or document reference. Since no additional context was provided, the translation maintains the exact alphanumeric format without expansion.)