原问题几乎相当于求1 ~ n的区间内，有多少个数是>=k的。 但是有一点不同的是，这些数是1 ~ n最小素因子。 直接上普通平衡树Treap。 有一点要注意的是，k在平衡树内不存在的情况，比赛的时候就因为这个我一直wawawa.....呜呜呜了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 5, INF = 1e9 + 7;
struct node{
    int r, k;
    int pos;
    bool operator < (const node &p) const {
        return r < p.r;
    }
} a[N];
int p[N];
int v[N];
int cnt = 0;
void init(int n)
{
    for (int i = 2; i <= n; i++){
        if (v[i]==0) {
            p[++cnt] = i;
            v[i] = i;
        }
        for (int j = 1; j <= cnt; j++){
            if(p[j] > v[i] || p[j] > n / i)break;
            v[i * p[j]] = p[j];
        }
    }
    /* for (int i = 1; i <= 15; i++) cout << v[i] << " ";
    cout << endl; */
}
int ans[N];
int n;
struct Node
{
    int l, r;
    int k;
    int val;//堆中的编号
    int cnt, size;
}tr[N];
int root, idx;
void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;//上传节点信息，更新size
}
int new_node(int k)
{
    tr[ ++ idx].k = k;
    tr[idx].val = rand();//尽量随机，随手给个就行
    tr[idx].cnt = 1;
    tr[idx].size = 1;
    return idx;
}
void zig(int &u)//左右旋，没啥好说的，自己在纸上画一下就知道了
{
    int q = tr[u].l;
    tr[u].l = tr[q].r;
    tr[q].r = u;
    u = q;
    pushup(tr[u].r);
    pushup(u);//最后一定要记得上传，不然完了
}
void zag(int &u)
{
    int q = tr[u].r;
    tr[u].r = tr[q].l;
    tr[q].l = u;
    u = q;
    pushup(tr[u].l);
    pushup(u);
}
void build()//建树操作，为了正确性增加两个哨兵，防止越界
{
    new_node(-INF), new_node(INF);
    root = 1, tr[1].r = 2;//初始化一下
    pushup(root);//上传信息
    if(tr[1].val< tr[2].val) zag(root);//不平衡了就旋转
}
void insert(int &u, int k)
{
    if(u == 0) u = new_node(k);//如果走到空了，就新建
    else
    {
        if(tr[u].k == k)//如果找到了相同的节点，就cnt++
        {
            tr[u].cnt ++;
        }
        else
        {
            if(tr[u].k > k)//否则看看是在左边还是在右边
            {
                insert(tr[u].l, k);
                if(tr[tr[u].l].val > tr[u].val) zig(u);//不平衡立马调整
            }
            else
            {
                insert(tr[u].r, k);
                if(tr[tr[u].r].val > tr[u].val) zag(u); 
            }
        }
    }
    pushup(u);//最后上传一下，是不是和线段树有点像啊？
}
void del(int &u, int k)//删除操作
{
    if(u == 0) return ;//如果没了说明节点不存在，就不管了。
    if(tr[u].k == k)//如果找到了这个点
    {
        if(tr[u].cnt > 1) tr[u].cnt --;//大于一好说，直接cnt --
        else//不大于一
        {
            if(tr[u].l || tr[u].r)//先看看是不是叶节点
            {
                if(!tr[u].r || tr[tr[u].l].val) 
                {
                    zig(u);
                    del(tr[u].r, k);//记得维护平衡哦
                }
                else
                {
                    zag(u);
                    del(tr[u].l, k);
                }
            }
            else u = 0;//是的话不用考虑平衡问题，直接删就是了
        }
    }
    else if(tr[u].k > k) del(tr[u].l, k);//如果没有找到就判断一下在左右两边的哪一边
    else del(tr[u].r, k);//找一下
    pushup(u);//上传更改
}
int get_rank(int u, int k)
{
    if(u == 0) return 0;//是0随便返回就行
    if(tr[u].k == k) return tr[tr[u].l].size + 1;//相等了那排名应该就是左边的数量加上自己
    if(tr[u].k > k) return get_rank(tr[u].l, k);//大了找左边
    return tr[tr[u].l].size + tr[u].cnt + get_rank(tr[u].r, k);//找右边
}
bitset<N> book;
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld", &a[i].r, &a[i].k);
        a[i].pos = i;
    }
    sort(a + 1, a + 1 + n);
    init(N);
    int now = 2;
    build();
    for (int i = 1; i <= n; i++){
        while(now<=a[i].r){
            insert(root, v[now]);
            book[v[now]] = 1;
            now++;
        }
        int rk = get_rank(root, a[i].k) - 1;
        if(book[a[i].k]) ans[a[i].pos] = a[i].r - 1 - (rk - 1);
        else ans[a[i].pos] = a[i].r - 1 - rk;
    }
    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;
}