题目描述

为了便于计算时间间隔，天文学中常用儒略日（Julian day）来表示日期。儒略日定义为从公元前 4713 年 1 月 1 日正午 12 时刻到目标时刻之间所经过的天数（不足一天用小数表示）。利用这一纪年方式，任意两个时刻都可以方便地计算差值。

现在给定一个整数儒略日（对应某一天的正午 12 时刻），请你计算它对应的公历日期。

现行公历为格里高利历（Gregorian calendar），于公元 1582 年由教皇格里高利十三世在儒略历基础上修订而成（注：儒略历与儒略日是不同的概念）。具体日期规则如下：

1. 公元 1582 年 10 月 15 日（含）之后：适用格里高利历。各月天数与常见公历一致。闰年规则：年份为 $400$ 的倍数，或为 $4$ 的倍数但不是 $100$ 的倍数时，该年为闰年，二月有 $29$ 天。
2. 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：这些日期不存在，10 月 4 日之后直接跳到 10 月 15 日。
3. 公元 1582 年 10 月 4 日（含）之前：适用儒略历，每月天数与格里高利历相同，但只要年份为 $4$ 的倍数即为闰年。
4. 尽管儒略历于公元前 45 年才开始实行，但人们习惯按儒略历最终规则反推所有 1582 年 10 月 4 日之前的时间。注意公元零年不存在，即公元前 $1$ 年的下一年是公元 $1$ 年。因此公元前 $1$ 年、前 $5$ 年、前 $9$ 年、前 $13$ 年……应视为闰年。

输入格式

第一行一个整数 $Q$，表示询问的组数。

接下来 $Q$ 行，每行一个非负整数 $r_i$，表示一个儒略日。

输出格式

对于每个儒略日 $r_i$，输出一行对应的日期字符串 $s_i$。格式如下：

1. 若为公元后年份，输出 Day Month Year，日、月、年均不含前导零，用空格分隔。例如公元 2020 年 11 月 7 日正午输出 7 11 2020。
2. 若为公元前年份，输出 Day Month Year BC，年份数值取绝对值。例如公元前 841 年 2 月 1 日正午输出 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

提示

【数据范围】