#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int N = 2e5;

vector<bool> sieve(N + 5, true);
vector<int> primes;
void gensieve()
{
    sieve[0] = sieve[1] = false;
    for (int i = 2; i <= sqrt(N); i++)
    {
        if (sieve[i])
        {
            for (int j = i * i; j <= N; j += i)
                sieve[j] = false;
        }
    }
    for (int i = 2; i <= N; i++)
    {
        if (sieve[i])
            primes.push_back(i);
    }
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int find(int limit, vector<int> &primeFactors)
{
    int valid = 0;
    int sz = primeFactors.size();
    for (int mask = 1; mask < (1 << sz); mask++)
    {
        int x = mask;
        int bit = 0;
        int product = 1;
        bool exceeded = false;

        while (x)
        {
            if (x & 1)
            {
                if (product > (limit / primeFactors[bit]))
                {
                    exceeded = true;
                    break;
                }
                product *= primeFactors[bit];
            }
            bit++;
            x >>= 1;
        }

        if (exceeded)
            continue;
        int parity = __builtin_popcount(mask);
        if (parity & 1)
        {
            valid += (limit / product);
        }
        else
        {
            valid -= (limit / product);
        }
    }
    return limit - valid;
}

void solve()
{
    int n, l, r;
    cin >> n >> l >> r;

    vector<int> primeFactors;

    for (auto p : primes)
    {
        if (n % p == 0)
        {
            primeFactors.push_back(p);
            while (n % p == 0)
            {
                n /= p;
            }
        }
    }
    if (n >= 2)
    {
        primeFactors.push_back(n);
    }

    int x = find(r, primeFactors);
    int y = find(l - 1, primeFactors);

    cout << x - y << endl;
}

signed main()
{
    fast();
    int t = 1;
    cin >> t;
    gensieve();
    while (t--)
    {
        solve();
    }
    return 0;
}