Solved very easily see -

```
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 10000050
#define lli long int
#define loop(i,n) for (lli i = 0; i < n; i++)
lli spf[MAX+1];
void sieve2(){ //smallest prime factor of N.
loop(i,MAX+1) spf[i]=i;
for(lli i=4;i<=MAX;i+=2) spf[i]=2;
for(lli i=3; i*i<=MAX; i++){
if (spf[i] == i){
for (int j=i*i; j<=MAX; j+=i)
if (spf[j]==j) //marking spf[j] if it is not previously marked
spf[j] = i;
}
}
}
```

```
lli tfactor[MAX+1];
lli sumfactor[MAX+1];
lli pre[MAX+1];
void sieve4(){ // totalfactor and sum_of_all_factors
// n = (a^p)*(b^q)*(c^r)....
// totalfactors = (p+1)*(q+1)*(r+1)...
// sumoffactors = [(a^(p+1)-1)/(a-1))]*[(b^(q+1)-1)/(b-1))]*[(c^(r+1)-1)/(c-1))]....
sieve2();
tfactor[1] = sumfactor[1] = pre[1] = 1;
for(lli i=2;i<=MAX;i++){
lli mspf = spf[i];
lli prim = mspf;
lli temp = i;
lli cnt=0;
while(temp%mspf==0){
temp/=mspf;
cnt+=1;
prim = prim*mspf;
}
tfactor[i] = (cnt+1) * tfactor[temp];
pre[i] = pre[i-1] + tfactor[i];
sumfactor[i] = (prim -1)/(mspf-1) * sumfactor[temp];
}
}
```

Now for each No. N (in query ) find the smallest index **i** such that pre[i]>= N , and how can i do this … we can do binary search here

```
int main(){
sieve4();
lli t;
cin>>t;
while(t--) {
lli n;
cin>>n;
lli ans = upper_bound(pre,pre+MAX,n) - pre;
cout<<ans-1<<endl;
}
return 0;
}
```