Teacher Mai 有一个包含 $n$ 个顶点的图，顶点编号从 $1$ 到 $n$。对于每一条边 $(u, v)$，其权重为 $\gcd(u, v)$（$\gcd(u, v)$ 表示 $u$ 和 $v$ 的最大公约数）。
你需要找到一个边集，使其构成一棵包含所有顶点的生成树，并使得树中所有边的权重之和最大。输出该最大权重和。
第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。
对于每个测试用例，仅包含一行，为一个整数 $n$ ($1 \le n \le 10^5$)。
对于每个测试用例，输出一个整数，表示答案。
5 1 2 3 4 5
0 1 2 4 5
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: