Jaw-Dropping Set

Time limit1sMemory limit256 MB

Summary

For each n up to 1e9, find the maximum size of a subset of {1..n} with no element dividing another, then the minimum possible sum among such maximum-size subsets.

Level: Medium6 of 10
Topics: Math, Number theory, Greedy, Combinatorics
Solved: No attempts yet

Problem

A subset $A$ of the set $\{1, 2, 3, \ldots, n\}$ is called interesting if for any pair of different integers $x, y \in A$ , neither $x$ divides $y$ nor $y$ divides $x$ .

An interesting subset $A$ is called amazing if it has the maximum cardinality among all interesting subsets.

Finally, an amazing subset $A$ is called jaw-dropping if it has the minimum sum of elements among all amazing subsets.

Given $n$ , find the sum of elements in a jaw-dropping subset of $\{1, 2, 3, \ldots, n\}$ .

Input

The first line contains the integer $t$ ( $1 \le t \le 10^5$ ), the number of test cases.

Each of the next $T$ lines contains an integer $n_i$ ( $1 \le n_i \le 10^9$ ).

Output

Print $T$ lines with the answer for each test case.

Examples1

Example 1
Input
```
7
1
2
3
4
5
6
7
```
Expected output
```
1
1
5
5
10
10
17
```