G

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
typedef long long ll;

const int mod = 1e9 + 7;
const int N = 1e6 + 4;

int n;
int smf[N];
long long L, R;
vector<int> pr;

long long calc(int cur, int cnt, int prod)
{
  if(cur >= sz(pr)){
    if(!cnt)
      return 0;
    int t = (cnt % 2 == 0 ? -1 : 1);
    return t * (R / prod - (L - 1) / prod);
  }
  return calc(cur + 1, cnt, prod) + calc(cur + 1, cnt + 1, prod * pr[cur]);
}

void pre()
{
  for(int i = 1 ; i < N ; i++)
    smf[i] = i;
  for(int i = 2 ; i * i < N ; i++){
    if(smf[i] == i){
      for(int j = 2 * i ; j < N ; j += i)
        smf[j] = min(smf[j], i);
    }
  }
}

int main()
{
    freopen("answer.in", "r", stdin);
  int T;
  cin >> T;
  pre();
  while(T--){
    cin >> n;
    cin >> L >> R;
    pr.clear();
    while(n > 1){
      int p = smf[n];
      pr.push_back(p);
      while(n % p == 0)
        n /= p;
    }
    cout << R - L + 1 - calc(0, 0, 1) << endl;
  }
  return 0;
}