Почти простые числа

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 3;
const long long M = 1e12;

int pr[N];

int main(){
    vector <long long> v;
    for (int i = 2; i < N; i++) {
        if (pr[i] == 0) {
            long long x = i;
            while (x * i <= M) {
                x = x * i;
                v.push_back(x);
            }
            if (1ll * i * i >= N) continue;
            for (int j = i * i; j < N; j += i) {
                pr[j]++;
            }
        }
    }

    int tt;
    cin >> tt;

    while (tt--) {
        long long low, high;
        cin >> low >> high;

        int cnt = 0;
        for (long long x : v) {
            if (x >= low && x <= high)
                cnt++;
        }

        cout << cnt << endl;
    }
}