9462: Good Tree

Given a tree where all edge weights are $\textstyle 1$, define $\textstyle f(u)=\sum_v dis(u,v)$, where $\textstyle v$ represents all nodes in the tree, and $\textstyle dis(u,v)$ is the length of the simple path between node $\textstyle u$ and node $\textstyle v$. A tree is called “good” if there exist two nodes $\textstyle u$ and $\textstyle v$ such that $\textstyle f(u)-f(v)=x$. Given integer $\textstyle x$, determine the minimum number of nodes required for the tree to be “good”.

Each test contains multiple test cases. The first line contains the number of test cases $\textstyle t$ ($\textstyle 1 \leq t \leq 10^5$). The description of the test cases follows. Each test case contains an integer $\textstyle x(1\le x\le 10^{18})$, representing the value for which you need to determine the minimum number of nodes required for the tree to be “good”.

For each test case, output a single integer, representing the minimum number of nodes required for the tree to be “good”. It can be shown that the answer always exists.