经过一系列的复杂计算及推演最终得出一个结论：任何x,y都会满足一个式子：

对任意K>=2,a[i] = pow(k,2) * a[i-1] - a[i-2],其中a[0]=0,a[1]=k。

那么我们只要枚举其中较大的那个数，打表后二分即可，由于a[2]=k^3,因此我们只需要枚举到1e6,时间复杂度1e6+Tlogn

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
vector<int> g;
const int maxn = 1e6;
int a[maxn];
signed main(){
    int t;
    cin >> t;
    for (int k = 2; k <= 1e6; ++k) {
        a[0] = 0;
        a[1] = k;
        for (int i = 2; i <= 60 ; ++i) {
            a[i] = pow(k,2) * a[i-1] - a[i-2];
            if(a[i]>1e18||a[i]<0)  break;
            g.push_back(a[i]);
        }
    }
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    while(t--){
        int n;
        cin >> n;
        cout << upper_bound(g.begin(),g.end(),n)-g.begin()+1<<endl;
    }
}