题目描述

33DAI 手上有 $t$ 个年份，每个年份都不小于 $2026$。他听说闰年的判定规则不只一种，于是想把这 $t$ 个年份在下面两种规则下各判定一次。

规则一（现行公历，即格里高利历）：年份 $y$ 是闰年，当且仅当

• （$y$ 能被 $4$ 整除，且 $y$ 不能被 $100$ 整除）；或
• （$y$ 能被 $400$ 整除）。

规则二：在规则一的基础上再加一条 —— 若 $y$ 能被 $3200$ 整除，则 $y$ 不是闰年。

也就是说，按规则二，$y$ 是闰年当且仅当 $y$ 在规则一下是闰年，并且 $y$ 不能被 $3200$ 整除。

33DAI 想知道：对每个年份，它在两种规则下分别是不是闰年。

输入格式

从标准输入读入数据。

输入的第一行是一个整数 $t$（$1 \le t \le 10^5$），表示年份的个数。

接下来 $t$ 行，每行一个整数 $y$（$2026 \le y \le 10^{18}$），表示一个年份。

输出格式

输出到标准输出。

输出 $t$ 行，顺序与输入一致。对每个年份输出一行两个整数 $a$ 与 $b$，用一个空格隔开：

• 若该年份在规则一下是闰年，则 $a = 1$，否则 $a = 0$；
• 若该年份在规则二下是闰年，则 $b = 1$，否则 $b = 0$。

1
2026

0 0

4
2028
2100
2400
2800

1 1
0 0
1 1
1 1

3
3200
3201
6400

1 0
0 0
1 0

样例解释

• 样例 1：$2026$ 不能被 $4$ 整除，所以在两种规则下都不是闰年。
• 样例 2：$2028$ 能被 $4$ 整除、不能被 $100$ 整除，是闰年；$2100$ 能被 $100$ 整除、不能被 $400$ 整除，不是闰年；$2400$ 与 $2800$ 都能被 $400$ 整除，是闰年。这四个年份都不能被 $3200$ 整除，因此两条规则给出的结果相同。
• 样例 3：$3200$ 能被 $400$ 整除，所以规则一下是闰年；它也能被 $3200$ 整除，所以规则二下不是闰年。$3201$ 不能被 $4$ 整除，两种规则下都不是闰年。$6400$ 能被 $400$ 整除、也能被 $3200$ 整除，所以规则一下是闰年、规则二下不是。

提示

• 本题输入量较大，建议使用较快的读入方式。
• 输出共 $t$ 行，每行两个整数之间用一个空格隔开。

数据范围

对于所有测试数据，保证 $1 \le t \le 10^5$，$2026 \le y \le 10^{18}$。

共 $15$ 个测试点，按测试点计分：子任务 $1$、$2$ 的每个测试点 $6$ 分，子任务 $3$ 的每个测试点 $8$ 分。