Problem Description

MX has a set $S=\{3,4,5,\cdots ,w\}$ containing $(w-2)$ numbers. You need to construct a set that contains only non-negative integers (with no repeated elements), such that every number in $S$ can be obtained by adding together at least $3$ different numbers from this set. Find the minimum number of elements this set must contain.

Input Format

This problem contains multiple groups of testdata.

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain an integer $w$.

Output Format

Output $T$ lines. Each line outputs an integer $n$, meaning the minimum number of elements the set should contain.

1
4

4

5
3
18
999
9999
9999999999

3
6
12
15
35

Hint

Sample 1 Explanation:

The set elements can be $0,1,2,3$.

Constraints:

This problem uses bundled tests.

For all testdata, it is guaranteed that $1\le T \le 10^5$ and $3\le w \le 10^{12}$.

Translated by ChatGPT 5