题目描述

Polycarp 喜欢正整数的平方数和立方数。下面是他喜欢的数列的开头：$1$，$4$，$8$，$9$，……

给定一个数字 $n$，请统计从 $1$ 到 $n$ 之间 Polycarp 喜欢的整数的个数。换句话说，找出有多少个 $x$ 满足 $x$ 是某个正整数的平方或立方（或者同时是平方和立方）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 20$），表示测试用例的数量。

接下来的 $t$ 行，每行一个整数 $n$（$1 \le n \le 10^9$），表示一个测试用例。

输出格式

对于每个测试用例，输出一个整数，表示从 $1$ 到 $n$ 之间 Polycarp 喜欢的整数的个数。

说明/提示

由 ChatGPT 4.1 翻译

样例

6
10
1
25
1000000000
999999999
500000000

4
1
6
32591
32590
23125