Divisor Cutter#13099
You are given a log of length . A log cutter machine processes logs by cutting a piece from it. The length of the cut piece is exactly the maximum proper divisor of the log's length (i.e., the largest divisor strictly less than the length itself). The machine then throws this cut piece away.
To minimize the total length of the wasted wood, you can initially split the log into several parts of lengths a_1, a_2, \dots, a_k such that \sum\limits_{i=1}^{k} a_i = n. The machine will then treat each part separately.
However, there is a catch: the machine cannot process logs of length . If any part has a length a_i = 1, the machine will malfunction and throw away all the logs you have collected. Therefore, you must ensure that every a_i > 1.
Find the minimum total length of the logs thrown away by the machine.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The only line of each test case contains a single integer (2 \le n \le 10^{9}) — the initial length of the log.
For each test case, print a single integer — the minimum total length of the logs thrown away by the machine.
Example 1
Subtask ( points): (\sum n \le 100)
Subtask ( points): (\sum n \le 10^5)
Subtask ( points): No additional constraints.