22968번 - 균형

이진 탐색 트리의 한 종류인 AVL Tree는 "높이 균형 성질"이라는 성질을 이용해 트리의 균형을 맞춘다.

또한, 높이 균형 성질을 만족하는 이진 탐색 트리는 전부 AVL Tree이다.

트리 $T$의 모든 내부 정점 $v$에 대해, $v$의 왼쪽 부트리와 오른쪽 부트리의 높이 차이가 1 이하일 때, $T$는 높이 균형 성질을 만족한다고 부른다.

위 그림에서, 왼쪽에 있는 트리는 모든 내부 정점의 왼쪽 부트리와 오른쪽 부트리의 높이가 동일하므로 AVL Tree이다.

가운데에 있는 트리는 5, 6, 8번 정점의 왼쪽 부트리와 오른쪽 부트리의 높이 차이는 1, 나머지 정점들은 0이므로 AVL Tree이다.

오른쪽에 있는 트리는 8번 정점의 왼쪽 부트리와 오른쪽 부트리의 높이 차이가 2이므로 AVL Tree가 아니다.

양의 정수 $V$가 주어지면, 최대 $V$개의 정점을 사용해서 만들 수 있는 AVL Tree의 최대 높이를 출력하는 프로그램을 작성하자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

둘째 줄부터 $T$개의 줄에 걸쳐 정점의 개수 $V$가 한 줄에 하나씩 주어진다.

총 $T$개의 줄에 걸쳐 정답을 출력한다.

각 테스트 케이스마다, 최대 $V$개의 정점으로 만들 수 있는 AVL Tree의 최대 높이를 출력한다.

• $1 \leq T \leq 1\,000$
• $1 \leq V \leq 1\,000\,000\,000$