#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod=998244353;
 
void solve() {
 
  ll k,l1,r1,l2,r2;
  cin >> k >> l1 >> r1 >> l2 >> r2;
  ll ans =0;
  int high=min(r1,r2);
  int low=max(l1,l2);
  ans+=max(0,high-low+1);
  ll test_k=k;
  while(test_k<=1e9){
    int upper=min(r1,r2/test_k);
    int lower=max(l1,(l2+test_k-1)/test_k);
    if(upper>=lower) ans+=upper-lower+1;
    test_k*=k;
  }
  cout << ans << '\n';
 
}
 
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) solve();
 
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwpjb25zdCBpbnQgTW9kPTk5ODI0NDM1MzsKCnZvaWQgc29sdmUoKSB7CgogIGxsIGssbDEscjEsbDIscjI7CiAgY2luID4+IGsgPj4gbDEgPj4gcjEgPj4gbDIgPj4gcjI7CiAgbGwgYW5zID0wOwogIGludCBoaWdoPW1pbihyMSxyMik7CiAgaW50IGxvdz1tYXgobDEsbDIpOwogIGFucys9bWF4KDAsaGlnaC1sb3crMSk7CiAgbGwgdGVzdF9rPWs7CiAgd2hpbGUodGVzdF9rPD0xZTkpewogICAgaW50IHVwcGVyPW1pbihyMSxyMi90ZXN0X2spOwogICAgaW50IGxvd2VyPW1heChsMSwobDIrdGVzdF9rLTEpL3Rlc3Rfayk7CiAgICBpZih1cHBlcj49bG93ZXIpIGFucys9dXBwZXItbG93ZXIrMTsKICAgIHRlc3Rfayo9azsKICB9CiAgY291dCA8PCBhbnMgPDwgJ1xuJzsKICAKfQoKaW50IG1haW4oKXsgCiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoJCiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkgc29sdmUoKTsKICAgIAoKICAgIHJldHVybiAwOwp9Cg==

NQoyIDIgNiAyIDEyCjIgMSAxMDAwMDAwMDAwIDEgMTAwMDAwMDAwMAozIDUgNyAxNSA2MwoxMDAwMDAwMDAwIDEgNSA2IDEwMDAwMDAwMDAKMTUgMTcgNzggMjU5NiAyMDkxNDg2MQo=

5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861