5275: Minimum spanning tree
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:24
解决:8
题目描述
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.
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.
输入
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.
The only line of each test case contains one integers n (2<=n<=10000000) as mentioned above.
输出
For each test case, print one integer in one line, which is the minimum spanning tree edge weight sum.
样例输入 复制
2
2
6
样例输出 复制
0
26