### 问题描述

在程序设计竞赛中，小蓝发现一个有趣的现象：除 $1$ 外的正整数经过几次方后就会炸 int。

小蓝现在有个长度为 $n$ 的数组 $x$，他想知道每个整数 $x_i$ 最少需要进行多少次方运算才会炸 int。

在 C++ 和 Java 中，int 类型变量的最大值是 $2^{31}-1$。如果一个 int 类型变量的值试图超过这个限制，就会发生溢出，这就是所谓的 "炸 int"。

输入格式

第一行输入一个正整数 $n$，代表小蓝手中的整数数量。

第二行输入 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示数组 $x$。

输出格式

输出共 $n$ 行，每行输出一个整数，代表对应的 $x$ 最少需要进行多少次方运算才会炸 int。

样例输入

5
2 3 4 5 6

样例输出

31
20
16
14
12

数据范围

对于所有的测试数据，满足 $1 \leq n \leq 10^5$，$2 \leq x_i \leq 10^9$。