题目描述

为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数。给定一个不含小数部分的儒略日，请你计算该儒略日所对应的公历日期。

现行公历为格里高利历，规则如下：

1. 公元 1582 年 10 月 15 日（含）以后：适用格里高利历，闰年规则为年份是 400 的倍数，或年份是 4 的倍数但不是 100 的倍数。
2. 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）不存在，10 月 4 日之后为 10 月 15 日。
3. 公元 1582 年 10 月 4 日（含）以前：适用儒略历，只要年份是 4 的倍数就是闰年。
4. 公元零年不存在，公元前 1 年的下一年是公元 1 年。公元前 1 年、前 5 年、前 9 年……为闰年。

输入格式

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

输出格式

对于每个 r_i 输出一行日期字符串：

• 公元后：Day Month Year
• 公元前：Day Month Year BC

日、月、年均不含前导零，中间用一个空格隔开。

样例 1

输入：

3
10
100
1000

输出：

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

样例 2

输入：

3
2000000
3000000
4000000

输出：

14 9 763
15 8 3501
12 7 6239

数据范围

• Q ≤ 10^5
• r_i 为非负整数，保证对应答案年份不超过 10^9
• r_i 在 64 位整数范围内