|
||||||||||
Minimum spanning treeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 2080 Accepted Submission(s): 912 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
Sample Output
Source | ||||||||||
|