Minimum spanning tree

Problem Description

Given n-1 points, numbered from 2 to n, the edge weight between the two points a and b is lcm(a, b). Please find the minimum spanning tree formed by them. A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. lcm(a, b) is the smallest positive integer that is divisible by both a and b.

Input

The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow. The only line of each test case contains one integers n (2<=n<=10000000) as mentioned above.

Output

For each test case, print one integer in one line, which is the minimum spanning tree edge weight sum.

Sample Input

2

2

6

Sample Output

0

26

Source

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