Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: 1, 4, 8, 9, ....
For a given number n, count the number of integers from 1 to n that Polycarp likes. In other words, find the number of such x that x is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).
Input
The first line contains an integer t (1≤t≤20) — the number of test cases.
Then tt lines contain the test cases, one per line. Each of the lines contains one integer nn (1≤n≤109).
Output
For each test case, print the answer you are looking for — the number of integers from 1 to nn that Polycarp likes.
Example
input
Copy
6 10 1 25 1000000000 999999999 500000000
output
Copy
4 1 6 32591 32590 23125
题意：从1到n之间有几个平方数和立方数
思路：将所有的平方数和立方数都压入set，然后遍历一遍即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
set<ll> se;
int main(){
ios::sync_with_stdio(false);
for(ll i = 1; i * i <= 1000000000; i++){
se.insert(i * i);
}
for(ll i = 1; i * i * i <= 1000000000; i++){
se.insert(i * i * i);
}
int t;
cin >> t;
int n;
while(t--){
cin >> n;
int ans = 0;
for(auto i : se){
if(n >= i){
ans++;
}else{
break;
}
}
cout << ans << endl;
}
return 0;
}