该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

拆分数是一个常见的数学问题，你需要将一个正整数 $m$ 拆分成若干个正整数的和。

形式化地，若有 $n$ 个正整数 $a_1, \ldots, a_n$ 满足 $\sum_{i=1}^{n} a_i=m$，则称这 $n$ 个正整数为正整数 $m$ 的一个拆分数。

但拆分数的规模（即有多少种不同的拆分数）究竟有多大是一个很难的问题，但你想到了一个基于如下式子的算法，你只要知道奇特值 $V$，其中 $V = n\sum_{i=1}^{n}a_i^2$，在不同拆分方案下的最小值和最大值，就可以通过枚举这些值知道总拆分方案数。

但只是计算这个规模也很难，你想知道对于给出的 $m$，在所有可能的拆分方案中所对应的奇特值 $V$ 的最小值和最大值。

Input

第一行给出一个整数 $T$（$1\le T \le 10^4$），表示数据组数。

对于每组数据，一行一个整数 $m$（$1\le m\le 10^6$），表示给出的正整数 $m$。

Output

对于每组数据，输出一行两个整数，表示不同拆分方案下，给出的正整数所对应的奇特值的最小值和最大值。

Samples

3
2
5
8

4 4
25 34
64 114