#P11770. 檐牙覆雪

檐牙覆雪

题目背景

为避免卡常,本题时限为比赛时的 2 倍。

“雨打在窗沿,下坠,一级一级。”

但这次是雪啦!天依与阿绫靠在窗边,赏着乍到的飞雪。

题目描述

还是熟悉的地方:一共有 nn 级窗沿,从高到低编号,最高层编号为 11,最底层编号为 nn。天依注意到,每一级窗沿上的积雪都可以看作包含若干雪团的可重集合,一开始,第 11 级窗沿上有一团体积为 11 的雪,其他窗沿上没有任何积雪。忽然,一阵夹杂着雪的风刮过,片刻间积雪产生了 nn 次变换——

ii 次变换中,第 ii 级窗沿上的每一团雪都会被卷起,由于奇妙的物理原因,所有编号是 ii 的整数倍(不包括 ii 自身)的窗沿都会接收到新的积雪。具体地,设一团被卷起的雪体积为 VV,则在上述窗沿中,编号最大者会得到一团体积为 V+1V+1 的积雪,次大者会得到一团体积为 V+2V+2 的积雪,以此类推。最后,被卷起的雪团神奇地回到第 ii 级窗沿,也就是说本次变换后,第 ii 级窗沿上的积雪没有任何变化。

阿绫知道天依正在好奇:nn 次变换之后,每级窗沿上体积最大的一团雪的总体积是多少呢?既然她们正静静赏雪,就由你来回答这个问题叭!

输入格式

第一行一个整数 TT,表示数据组数。

2T+12\sim T+1 行每行一个整数,分别表示每组数据的 nn

输出格式

TT 行,分别表示每组数据的答案。

5
1
5
3
114514
2000000
1
18
6
18057023450
5575638612615

提示

样例解释

n=5n=5 时的终态如下:

11 级窗沿上有体积为 11 的雪团;
22 级窗沿上有体积为 55 的雪团;
33 级窗沿上有体积为 44 的雪团;
44 级窗沿上有体积为 3,63,6 的雪团;
55 级窗沿上有体积为 22 的雪团;

体积最大值之和为 1+5+4+6+2=181+5+4+6+2=18

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 100%100\% 的数据,1T5×1051\le T\le5\times10^51n2×1061\le n\le2\times10^6

对于不同的子任务,作如下约定:

子任务编号 TT nn 子任务分值
11 100\leq 100 3×104\leq 3\times10^4 1515
22 2×106\leq 2\times10^6 3535
33 3×104\leq 3\times10^4 1515
44 2×105\leq 2\times10^5
55 5×105\leq 5\times10^5 2×106\leq 2\times 10^6 2020