时间限制： 1.0 秒

空间限制： 512 MB

题目描述

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中，任何节点的两个子树高度相差不超过 1。

由于 AVL 树并非理想平衡而是适度平衡，因此对于规模同为 $n$ 的 AVL 树可以有不同高度。

定义只有一个节点的 AVL 树高为 0，那么对于 $n=7$ 的情况则有以下结构：

因此对于节点规模为 7 的二叉树，最大高度为 3。

给定 AVL 树的节点规模 $n$，你需要计算其最大高度是多少。

输入格式

从标准输入读入数据。

第一行输入一个整数 $T$，表示询问次数。

接下来 $T$ 行，每行一个正整数 $n$，表示询问的节点规模。

输出格式

输出到标准输出。

对于每个询问，输出一行一个非负整数，表示 AVL 树的最大高度。

2
1
2

0
1

子任务

对于所有数据，保证查询次数 $T\le 2\times 10^6$，查询的规模 $1\le n\le 10^9$。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

习题解析 7-13，fib-AVL

fib-AVL 也有很多其他性质，例如所有内部节点的平衡因子都不是 0。

来源

HDU 2193