OIG XV - sil

// https://szkopul.edu.pl/problemset/problem/QZaK6VS_X5JQ5HDcASAnpNFf/site/?key=statement
// XV OIJ (3 etap)

#include <algorithm>
#include <array>
#include <iostream>
#include <set>
#include <vector>

std::array<long long, 16> silnie = {
    1ll,     1ll,      2ll,       6ll,        24ll,        120ll,        720ll,         5040ll,
    40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll, 6227020800ll, 87178291200ll, 1307674368000ll,
};

std::vector<long long> v = {1, 2, 3};

long long pref[100 * 1000];

void generate() {
    for (int i = 3; i < silnie.size(); i++) {
        std::vector<long long> temp = {silnie[i]};

        for (const auto& num : v) {
            temp.push_back(num + silnie[i]);
        }

        for (const auto& num : temp) {
            v.push_back(num);
        }
    }

    std::sort(v.begin(), v.end());

    pref[0] = 0;
    for (int i = 1; i <= v.size(); i++) {
        pref[i] = pref[i - 1] + v[i - 1];
    }
}

int BS(long long a) {
    int p = 0, k = v.size() - 1, s;
    while (p < k) {
        s = (p + k) / 2;
        if (v[s] >= a) {
            k = s;
        } else {
            p = s + 1;
        }
    }
    return p;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    generate();

    int q;
    std::cin >> q;

    for (; q > 0; q--) {
        long long a, b;
        std::cin >> a >> b;

        int start_index = BS(a);
        int end_index = BS(b);
        long long sum = 0;

        if (v[end_index] > b) {
            end_index--;
        }

        if (v[start_index] < a) {
            start_index++;
        }

        sum += pref[end_index + 1] - pref[start_index];

        std::cout << sum << '\n';
    }

    return 0;
}