### 问题描述

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

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