#include <bits/stdc++.h>

using namespace std;

vector< pair<int, int> > p[21];

__int128 C(int n, int m) {
    __int128 res = 1;
    for (int i = 1; i <= m; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int qr(int r, int n, int m) {
    int res = 0;
    for (int i = 2; i <= m; ++i) if (!p[i].empty()) {
        int L = 0, R = p[i].size() - 1, z = -1;
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (p[i][mid].first <= n && p[i][mid].second <= r) {
                z = mid, L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        res += z + 1;
    }
    return res;
}

unordered_map<int, vector< pair<int, int> > > M, M2;

signed main() {
    for (int i = 1; i <= 100000; ++i) {
        for (int j = 2; j <= i / 2 && C(i, j) <= 1e9; ++j) {
            p[j].push_back(make_pair(i, C(i, j)));
            M[C(i, j)].push_back({i, j});
        }
    }
    for (auto [x, y] : M) if (y.size() >= 2) {
        M2[x] = y;
    }
    int T; scanf("%d", &T);
    while (T--) {
        int l, r, n, m, res = 0; scanf("%d%d%d%d", &l, &r, &n, &m);
        if (n >= l) {
            res += min(r, n) - l + 1;
            l = n + 1;
        }
        if (l > r || m == 1) { printf("%d\n", res); continue;}
        m = min(m, 20);
        res += qr(r, n, m) - qr(l - 1, n, m);
        for (auto [x, y] : M2) {
            int S = 0, f = 0;
            for (auto [a, b] : y) {
                S += (x >= l && x <= r && a <= n && b <= m);
                f |= (x >= l && x <= r && a <= n && b <= m);
            }
            res = res - S + f;
        }
        printf("%d\n", res);
    }
    return 0;
}