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.

Format

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.

Samples

2
2
6

0
26