P4583 [FJOI2015] World Tree

After Odin slew the giant Ymir, a gigantic ash tree grew from Ymir’s corpse. It became the core of the universe and is called the World Tree. The branches of this colossal tree form the entire world, guarded by mysterious arcane power. Odin discovered that each node of the World Tree has at most two subtrees. Its arcane power equals the maximum arcane power among its subtrees $+1$. If a node has no subtree, its arcane power is $1$; such nodes are called "sources". Over the long ages, the World Tree has formed a delicate magical balance: the absolute difference between the arcane powers of the left and right subtrees does not exceed $1$. If a node has only one subtree (say, the left subtree), then the arcane power of the right subtree is treated as $0$. Now Odin wants to know: in a World Tree with $n$ nodes, what is the maximum possible difference between the depths of the deepest and the shallowest two "sources" (i.e., leaf nodes)?

The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains an integer $n$, the number of nodes in the World Tree.

Output $T$ lines. Each line contains a single integer: the maximum possible difference between the depths of the deepest and the shallowest "sources".

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 10^{10000}$, $T \leq 50$. Translated by ChatGPT 5