题目描述

有一个形如 $\dfrac{0}{x}$ 的分数，重复以下步骤直到这个分数为 $1$：

1. 分子 $+1$。
2. 如果这个分数可以约分，约分到最简形式。

设 $f(x)$ 表示将 $\dfrac{0}{x}$ 变成 $1$ 的操作次数，现在请你求出 $n$ 以内 $f(x)$ 的最大值。

输入格式

第一行一个正整数 $T$，表示有 $T$ 组数据。

对于每组数据，一个正整数 $n$。

输出格式

输出答案。

5
1
2
5
8
114514

1
2
5
7
114493

数据范围

$1 \le T \le 5 \times 10^5$

$1 \le n \le 2\times 10^6$