题目描述

比赛期间，每支队伍都有一个计时器，目标是尽快将剩余时间用到 $0$ 。在 $0$ (秒)开始时，OMS 会在 $[1, T]$ 中均匀随机地生成一个整数 $t_0$ ，并将计时器的剩余时间初始化为 $t_0$ 秒。接下来，在每秒结束时(从第 $0$ 秒开始)，会依次发生以下事件：

• 计时器的剩余时间将减少 $1$ 。如果此时计时器的剩余时间为零，那么从比赛开始到此时的秒数就是你的罚时。
• 否则，您可以在此之后什么也不做，或者使用一次 OMS 上的刷新操作。如果您选择刷新计时器，OMS 将在 $[1, T]$ 中统一随机生成一个新整数 $t'$ ，并将您的计时器剩余时间设置为 $t'$ 。

您的目标是最小化惩罚。请使用最优策略计算预期罚分。在比赛过程中，您始终知道计时器的剩余时间以及 $T$ 的值。

输入格式

第一行包含一个整数 $n (1\le n\le 10^6)$ ，代表测试用例的数量。

在接下来的 $n$ 行中，每行都包含一个整数 $T_i (1\le T_i\le 10^9)$ ，代表 $i$ -th 测试用例的随机数生成间隔为 $[1,T_i]$ 。

输出格式

对于每个测试案例，输出一行包含两个正整数 $x_i,y_i$ ，其中 $\text{gcd}(x_i,y_i)=1$ 代表使用最优策略的预期惩罚为 $x_i/y_i$ 。可以证明，答案总是可以用分数来描述。

样例

3
1
2
3

1 1
3 2
2 1