Description

To make calculations easier, astronomers use the Julian day (Julian day) to represent time. A Julian day is defined as the number of days that have passed from 12:00 noon on January 1, 4713 BC to some later moment. If it is less than one full day, it is written as a decimal. With this astronomical calendar, every moment is mapped evenly onto a number line, so it is convenient to compute differences between times.

Now you are given a Julian day with no fractional part. Please compute the corresponding Gregorian calendar date for that Julian day (it must be 12:00 noon of some day).

The calendar we use today is the Gregorian calendar. It was introduced in AD 1582 by Pope Gregory XIII as a modification of the earlier Julian calendar (note: the Julian calendar is not directly related to the Julian day). Specifically, dates are determined by the following rules:

1. On and after October 15, 1582 (inclusive): use the Gregorian calendar. The number of days in each month is: 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. In leap years, February has $29$ days; otherwise it has $28$ days. 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. October 5, 1582 (inclusive) to October 14, 1582 (inclusive): these dates do not exist. These dates were removed, so the day after October 4 is October 15.
3. On and before October 4, 1582 (inclusive): use the Julian calendar. The days in each month are the same as in the Gregorian calendar, but a year is a leap year as long as it is a multiple of $4$.
4. Although the Julian calendar was only introduced in 45 BC, and there were some adjustments in its early period, today people are used to extending the final Julian calendar rules backward for all dates before October 4, 1582. Note that there is no year 0, i.e., the year after 1 BC is AD 1. Therefore, years such as 1 BC, 5 BC, 9 BC, 13 BC, ... should be treated as leap years.

Input Format

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

Output Format

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

1. If the year is AD, output Day Month Year. The day (Day), month (Month), and year (Year) have no leading zeros, and are separated by one space. For example, for 12:00 noon on November 7, 2020 AD, output 7 11 2020.
2. If the year is BC, output Day Month Year BC. The year (Year) should be the numeric value of that year; the rest is the same as the AD format. For example, for 12:00 noon on February 1, 841 BC, output 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

见附件中的 julian/julian3.in

见附件中的 julian/julian3.ans

Hint

Constraints

Translated by ChatGPT 5