$O(1)$ 容斥

好整数不能被任何一位数的质数（2,3,5,7）整除。

容斥原理：

计算区间内被 $2,3,5,7$ 整除的数的数量

使用容斥原理排除这些数，剩下的就是好整数

数学推导：

好整数数量 = 区间总数 - 被$2,3,5,7$ 整除的数的并集

使用位运算枚举所有可能的质数组合

关键公式：

被至少一个一位质数整除的数的数量 = Σ(被单个质数整除) - Σ(被两个质数整除) + Σ(被三个质数整除) - 被四个质数整除

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

const int N = 2e5 + 10, mod = 1e9 + 7;

int a[] = {2, 3, 5 ,7};
LL l, r;

int cal(int x)
{
    int ans = 0;
    while(x)
    {
        if(x & 1) ans ++;
        x >>= 1;
    }
    return ans;
}

LL good(LL n) //1~n不好数的数量
{
    LL ans = 0;
    for(int i = 1; i < (1 << 4); i ++)
    {
        int mul = 1;
        for(int j = 0; j < 4; j ++)
        {
            if((i >> j) & 1)
                mul *= a[j];
        }
        if(cal(i) & 1) ans += n / mul;
        else ans -= n / mul;
        // cout << "--" << mul << ' ' << ans << endl;
    }
    return ans;
}

void solve()
{
    cin >> l >> r;
    // if(l <= 9) l = 9, r = max(r, 9ll);
    LL x = l - 1 - good(l - 1), y = r - good(r);
    // cout << x << ' ' << y << endl;
    cout << y - x << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	int t = 1;
	cin >> t;
	while(t --)
		solve();
}