欢迎参加今年的互联网连接练习赛（ICPC）！在比赛中，你和你的队友将与障碍制造系统（OMS）进行对抗，以成功连接到服务器！请小心每一次刷新操作，因为系统可能会为你分配未知的障碍。

为了简化问题，我们将比赛过程建模如下：

每支队伍在比赛期间都有一个计时器，目标是尽快将剩余时间变为 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$ 个测试用例中生成随机数的区间为 $[1, T_i]$。

输出格式

对于每个测试用例，输出一行，包含两个正整数 $x_i, y_i$，满足 $\gcd(x_i, y_i) = 1$，表示最优策略下的期望罚时为 $x_i/y_i$。可以证明答案总能表示为一个分数。

样例

输入 1

3
1
2
3

输出 1

1 1
3 2
2 1