[FJOI2015] 世界树
题目描述
奥丁杀死的巨人伊米尔后,从伊米尔的尸体上生长出来一株巨大的梣树,它是整个宇宙的核心,被称为世界之树,这个巨木的枝干构成了整个世界,它被神秘的奥术力量所守护。
奥丁发现,世界树的每个节点至多有两棵子树,其蕴含的奥术力量是子树奥术力量的最大值 $+1$,如果一个节点没有子树,其奥术力量为 $1$,这些节点被称为“源”。
世界树在悠长的岁月里形成了奇妙的魔法平衡,具体来说,它的左子树与右子树的奥术力量的差的绝对值不会超过 $1$。若一个节点只有一棵子树(不妨设为左子树),则右子树的奥术力量视为 $0$。
现在奥丁想知道,在 $n$ 个节点的世界树中,最高和最低的两个“源”(即叶子节点)的深度差最大是多少?
输入输出格式
输入格式
第一行一个整数 $T$,表示数据组数。
以下 $T$ 行,每行一个整数 $n$ 表示世界树的节点数。
输出格式
$T$ 行,每行一个整数表示任意两个“源”的奥术力量的差的最大值。
输入输出样例
输入样例 #1
2
5
12345
输出样例 #1
1
9
说明
对于 $100\%$ 的数据,$1\leq n\leq 10^{10000}$,$T\leq 50$。