题目描述

小k 喜欢正整数的平方数和立方数。他喜欢的数字序列开头如下：$1, 4, 8, 9, ...$。

对于给定的数字 $n$，请计算区间 $[1,n]$ 中 小k 喜欢的整数数量。

换句话说，找出满足以下条件的 $x$ 的数量： $x$ 是某个正整数的平方，或某个正整数的立方（或同时满足两者，即既是平方数又是立方数）。

输入格式

• 第一行包含一个整数 $t (1≤t≤20)$，表示测试用例的数量。
• 接下来 $t$ 行，每行包含一个整数 $n$ $(1≤n≤10^9)$ 。

输出格式

每个测试用例，输出一个整数表示答案。

6
10
1
25
1000000000
999999999
500000000

4
1
6
32591
32590
23125

提示