F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Minimum spanning tree

Time 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
2 2 6
 

Sample Output
0 26
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 20:23:50, Gzip enabled