P9435 "XYGOI round1" Three Numbers

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.

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 $T$ lines. Each line outputs an integer $n$, meaning the minimum number of elements the set should contain.

#### 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}$. | Subtask | $T$ | $w$ | Score | |:-:|:-:|:-:|:-:| |0|$=1$|$w\le 10$|5| |1|$1\le T\le 10^3$|$w\le 20$|10| |2|$1\le T\le 50$|$w\le 10^{3}$|25| |3|$1\le T\le 10^3$|$w\le 10^{5}$|30| |4|$1\le T\le 10^5$|$3\le w\le 10^{12}$|30| Translated by ChatGPT 5