To simplify calculations, astronomers use the Julian day to express time. The Julian day is defined as the number of days that have elapsed since 12:00 noon on January 1, 4713 BC, with fractions of a day expressed as decimals. Using this astronomical calendar, every moment is mapped uniformly onto a number line, making it easy to calculate the difference between them.

Given a Julian day without a fractional part, please help calculate the corresponding Gregorian calendar date (which is always 12:00 noon on a certain day).

Our current calendar is the Gregorian calendar, which was modified from the original Julian calendar by Pope Gregory XIII in 1582 AD (note: the Julian calendar has no direct relationship with the Julian day). Specifically, the current calendar dates are calculated according to the following rules:

1. After (and including) October 15, 1582 AD: The Gregorian calendar is used. 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. 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. October 4, 1582 was followed by October 15, 1582.
3. Before (and including) October 4, 1582 AD: The Julian calendar is used. The number of days in each month is the same as in the Gregorian calendar, but any year that is a multiple of 4 is a leap year.
4. Although the Julian calendar was only implemented in 45 BC and underwent several adjustments in its early stages, it is common practice today to extrapolate all dates before October 4, 1582, according to the final rules of the Julian calendar. Note that there is no year 0; the year after 1 BC is 1 AD. Therefore, 1 BC, 5 BC, 9 BC, 13 BC, and so on, are considered leap years.

Input

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

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

1. If the year is AD, the format is Day Month Year. The day (Day), month (Month), and year (Year) do not contain 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 format is Day Month Year BC. The year (Year) is the numerical value of the year, and the rest is the same as for AD. For example: 12:00 noon on February 1, 841 BC is output as 1 2 841 BC.

Examples

Input 1

3
10
100
1000

Output 1

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

Input 2

3
2000000
3000000
4000000

Output 2

14 9 763
15 8 3501
12 7 6239

Examples 3

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

Data Range and Hints