Description

给定 $n-1$ 个点，编号为 $2$ 到 $n$，两点 $a$ 和 $b$ 之间的边权为 $\mathrm{lcm}(a, b)$。请求出由这些点构成的最小生成树。

最小生成树是指一张连通的带权无向图中，能够将所有顶点连接在一起、不含环且边权总和最小的边集。也就是说，它是边权之和尽可能小的一棵生成树。

$\mathrm{lcm}(a, b)$ 表示能同时被 $a$ 和 $b$ 整除的最小正整数（即最小公倍数）。

Format

Input

第一行包含一个整数 $t$（$t \leq 100$），表示测试数据的组数。接下来是 $t$ 组测试数据。

每组测试数据只有一行，包含一个整数 $n$（$2 \leq n \leq 10^7$），含义如上所述。

Output

对于每组测试数据，输出一行一个整数，表示最小生成树的边权之和。

Samples

2
2
6

0
26

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）