Shaban is moving from Earth to Mars, where the laws of physics are a little unusual.
On Earth, when several weights are placed on the same side of a balance scale, their weights are added together. For example, weights $$$2$$$ and $$$5$$$ have total weight $$$2 + 5 = 7$$$.
On Mars, however, weights are multiplied instead of added. Thus weights $$$2$$$ and $$$5$$$ have total weight $$$2 \cdot 5 = 10$$$.
 |
Shaban wants to take a collection of balance weights with positive integer values to Mars. For every vegetable whose weight is an integer from $$$1$$$ to $$$m$$$, inclusive, he must be able to determine its exact weight by placing a non-empty subset of his weights on the empty side of the balance. On Mars, this means that the product of the chosen weights must be equal to the vegetable's weight.
Multiple carried weights may have the same value.
Your task is to find the minimum number of weights Shaban needs to take.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case begins with a line containing one integer $$$m$$$ ($$$1 \le m \le 10^6$$$).
For each test case, print one integer — the minimum number of weights Shaban needs to take so that every integer weight from $$$1$$$ to $$$m$$$ can be represented as the product of a non-empty subset of his weights.
269
57
For $$$m = 6$$$, one optimal collection is $$$\{1, 2, 3, 4, 5\}$$$. The weight $$$1$$$ is necessary because the chosen subset must be non-empty. The weights $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$5$$$ are represented directly, and $$$6 = 2 \cdot 3$$$.
For $$$m = 9$$$, one optimal collection is $$$\{1, 2, 3, 4, 5, 7, 9\}$$$. In particular, $$$8 = 2 \cdot 4$$$ and $$$9$$$ is represented directly.
