D. Permutation with MAX Score
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

一个长度为 $$$n$$$ 的排列 $$$p$$$ 的得分计算方式如下：

  • 首先，你先确定一个正整数 $$$k$$$
  • 然后，对于每一个大于等于 $$$2$$$ 的位置 $$$i$$$，计算排列 $$$p$$$ 中下标从 $$$1$$$ 到 $$$i-1$$$ 的所有元素的和，计为 $$$s_i$$$
  • 如果 $$$p_i=k\times s_i$$$，那么排列 $$$p$$$ 的得分加 $$$1$$$。

给定一个整数 $$$n$$$，假如你可以任意选择 $$$k$$$，请你求出在所有长度为 $$$n$$$ 的排列中，得分最大的排列的得分是多少。

一个长度为 $$$n$$$ 的排列 $$$p$$$ 是指从 $$$1$$$ 到 $$$n$$$ 的每个整数恰巧在 $$$p$$$ 中出现一次，例如 $$$[3,1,2]$$$、$$$[1]$$$ 都是排列，但是 $$$[1,1,3]$$$、$$$[3,2,4]$$$ 都不是排列。

Input

第一行，一个整数 $$$t(1\le t\le 10^5)$$$，代表数据组数。

对于每组数据，仅输入一个正整数 $$$n(2\le n\le 10^{18})$$$，代表排列的长度。

由于这题输入数据的值比较大，所以你可能需要使用能够表示更大数据的数据类型，例如 C++ 中的 long long。

Output

对于每组数据，输出一个整数，代表在确定 $$$k$$$ 的情况下，长度为 $$$n$$$ 的排列的得分最多是多少。

Example
Input
6
2
3
7
916
5201314114514
1000000000000000000
Output
1
1
2
9
41
59
Note

对于样例第一组数据，选择 $$$k=2$$$，此时得分最高的排列为 $$$[1,{\color{red}2}]$$$，这个排列的得分为 $$$1$$$。

对于样例第三组数据，选择 $$$k=1$$$，此时得分最高的排列为 $$$[2,1,{\color{red}3},{\color{red}6},7,4,5]$$$。

对于 $$$i=2$$$，$$$1\neq 1\times 2$$$，所以这个位置不得分。

对于 $$$i=3$$$，$$$3 = 1\times (2+1)$$$，所以这个位置得分。

对于 $$$i=4$$$，$$$6 = 1\times (2+1+3)$$$，所以这个位置得分。

对于 $$$i=5$$$，$$$7\neq 1\times (2+1+3+6)$$$，所以这个位置不得分。

对于 $$$i=6$$$，$$$4\neq 1\times (2+1+3+6+7)$$$，所以这个位置不得分。

对于 $$$i=7$$$，$$$5\neq 1\times (2+1+3+6+7+4)$$$，所以这个位置不得分。

最终，这个排列的得分为 $$$0+1+1+0+0+0=2$$$。