#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
 
int cover(int l1, int r1, int l2, int r2){
    return max(min(r1, r2) - max(l1, l2) + 1, 0);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int k, l1, r1, l2, r2, sum = 0;
        cin >> k >> l1 >> r1 >> l2 >> r2;
        while(r2 >= l1){
            sum += max(min(r1, r2) - max(l1, l2) + 1, 0);
            l2 = (l2 + k - 1)/k;
            r2 = r2 / k;
        }
        cout << sum << endl;
    }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNvdmVyKGludCBsMSwgaW50IHIxLCBpbnQgbDIsIGludCByMil7CiAgICByZXR1cm4gbWF4KG1pbihyMSwgcjIpIC0gbWF4KGwxLCBsMikgKyAxLCAwKTsKfQoKaW50IG1haW4oKSB7CiAgICBjaW4udGllKDApLT5zeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkgewogICAgICAgIGludCBrLCBsMSwgcjEsIGwyLCByMiwgc3VtID0gMDsKICAgICAgICBjaW4gPj4gayA+PiBsMSA+PiByMSA+PiBsMiA+PiByMjsKICAgICAgICB3aGlsZShyMiA+PSBsMSl7CiAgICAgICAgICAgIHN1bSArPSBtYXgobWluKHIxLCByMikgLSBtYXgobDEsIGwyKSArIDEsIDApOwogICAgICAgICAgICBsMiA9IChsMiArIGsgLSAxKS9rOwogICAgICAgICAgICByMiA9IHIyIC8gazsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBzdW0gPDwgZW5kbDsKICAgIH0KfQ==

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