当前没有测试数据。

题目描述

Uim 喜欢分块，于是小 L 给了你一个正整数 $n$，你需要统计有多少个不超过 $n$ 的正整数 $x$ 满足 $\lceil \sqrt{x} \rceil$ 是 $x$ 的因数。

因为小 L 怕你浑水摸鱼，所以小 L 给了你 $q$ 组不同的询问 $n_1, \ldots, n_q$，每组询问的 $n_i$ 可能不同。你需要对每个 $n = n_i$ 求出正确答案。

题面中的 $\lceil \rceil$ 为向上取整符号，$\lceil a \rceil$ 表示最小的不小于 $a$ 的整数。例如，$\lceil 1.9\rceil = 2$，$\lceil 7 \rceil = 7$，而 $\lceil \pi \rceil = 4$。

输入格式

第一行，一个整数 $q$。

接下来 $q$ 行，第 $i$ 行一个正整数 $n_i$，表示第 $i$ 组询问对应的 $n$ 的值。

输出格式

输出共 $q$ 行。

第 $i$ 行输出一个整数，表示 $n = n_i$ 时小 L 的问题的答案。

输入输出样例

输入输出样例 #1

5
1
3
6
10
15

1
2
4
5
6

数据规模及约定

对于 $100\%$ 的数据，保证 $1 \leq q \leq 10^5， 1 \leq n_i \leq 10^{18}$。