Hint: the last sample of this problem is the maximum case.
If the sample includes the maximum case, you can observe something or check if your program works correctly for the maximum case (before submitting.)

In case of this problem, the answer to this problem turns out to be about \(2 \times 10^9\). Thus, we can observe that:

• enumerating all conforming integers is a bit reckless;
• if we can enumerate the answer effectively, for example with the meet-in-the-middle trick, it will finish in the execution time limit.

We consider adopting the meet-in-the-middle trick. How can we do that?

• Prepare arrays \(U=(1)\) and \(V=(1)\).
• For all primes \(q\) between \(2\) and \(P\), repeat the following.
  • Apply the following operation against \(W\), which is the smaller of \(U\) and \(V\).
    • Insert all integers not exceeding \(N\) obtained by multiplying each element of \(W\) by a power of \(q\).
• Finally, count the number of pairs taken from \(U\) and \(V\) whose product do not exceed \(N\), just as the merging process of the meet-in-the-middle trick.

In other words, we divide the prime factors up to \(P\) into two groups, enumerate the integers whose prime factors are only in one of them, and then merge them to count the integers whose prime factors are only in the sum set of them.

While it is difficult to estimate the complexity of this solution by hand, we can actually implement and try the maximum case to see that \(|U|,|V| \le 5 \times 10^6\) approximately, to see that sorting them and merging is still fast enough.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

void step(vector<long long> &a,long long p,long long mxm){
  long long sz=a.size();
  for(long long i=0;i<sz;i++){
    long long ad=a[i];
    while(1){
      ad*=p;
      if(ad>mxm){break;}
      a.push_back(ad);
    }
  }
}

int main(){
  vector<long long> pl={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
  long long n,p;
  cin >> n >> p;
  while(p<pl.back()){pl.pop_back();}

  vector<long long> u={1},v={1};
  for(auto &nx : pl){
    if(u.size()<v.size()){step(u,nx,n);}
    else{step(v,nx,n);}
  }
  // cerr << u.size() << " " << v.size() << "\n";

  sort(u.begin(),u.end());
  sort(v.begin(),v.end());
  long long res=0,j=v.size()-1;
  for(long long i=0;i<u.size();i++){
    long long mv=(n/u[i]);
    while(j>=0 && mv<v[j]){j--;}
    if(j<0){break;}
    res+=(j+1);
  }
  cout << res << "\n";
  return 0;
}