题目：https://vjudge.ppsucxtt.cn/contest/455985#problem/G
题意：有T组数据。数的区间[L,R]，在进制区间[l,r]内是回文串的个数。意思就是给一个数的区间[L,R]，然后又给了一个进制区间[l,r]，问在数的区间内，转化成对应的进制后，有多少个数是回文串，是回文串的话，给答案的贡献就是那个进制，否则就是1。比如3在十进制是个回文串，对答案的贡献就是10.它转化成2进制后是11，也是回文串，对答案的贡献是2。
1<=T<=1e5，1<=L<=R<=1e9，2<=l<=r<=36。
3 （1 1 2 36 —665) (1 982180 10 10----1000000)
(496690841 524639270 5 20—447525746)

题解：数位dp。
首先，询问区间[L,R]满足条件的数量，其实就是[0,R]-[0,L-1]的数量。
其次，每确定一个高位，相对应的低位也就确定了(回文串)。如果总共位数是8位，那么在[0,R]区间内的话，7位、6为----1位里面的回文串都是答案，这个时候就需要一个预处理一个数组了， f[k][i][j] 首先看i和j，意义为，总共有i位，最高位为j的可以形成的方案总数,再加上k，k的意义为，在进制为k的情况下。所以总的意义为，在k进制下，总共有i位，最高位为j可以形成的方案总数。
然后，有了上面那个数组和概念后，就可以套数位dp的框架了，首先肯定要枚举[l,r]这个进制，然后把对应的R转换为对应的进制的数。假如R有8位的话，枚举最高位的时候，不要枚举最高位为0，会有问题，最高位为0的情况，直接在下面暴力跑出答案即可，就是7-6-5-4-3-2-1位的所有情况。现在只是处理8位的情况即可，所以最高位不能枚举0，其它位就可以从0开始枚举了。假设某一位(不是最高位)是x的话，就可以枚举这一位为[0,x-1]，然后叠加f数组即可。这里要注意，每确定一个高位，其实对应的低位也就确定了(回文串)，所以其实只要枚举位数的一半即可，还有一些其他细节，详见代码。
可以参考一下这个题的解，有一定相似之处

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define ms(a, b) memset((a), (b), sizeof(a))
#define x first
#define y second
typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;

// f[k][i][j] 首先看i和j，意义为，总共有i位，最高位为j的可以形成的方案总数
//再加上k，k的意义为，在进制为k的情况下。所以总的意义为，在k进制下，总共有i位
//最高位为j可以形成的方案总数
int f[50][50][50];
int L, R, l, r;
//进制转换
vector<int> base(int n, int b) {
    vector<int> num;
    while (n) {
        num.emplace_back(n % b);
        n /= b;
    }
    while (num.size() > 1 && num.back() == 0) num.pop_back();
    return num;
}
//预处理f数组
void init(int base, int n) {
    // base是进制，n是多少位，首先预处理好0,1,2位
    for (int i = 0; i < base; i++)
        f[base][0][i] = f[base][1][i] = 1, f[base][2][i] = 1;
    //下面开始跑后面的位，因为最高位确定了，其实最低位也就确定了
    //所以每次往前面找两位即可
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < base; j++) {
            for (int k = 0; k < base; k++) {
                if (i - 2 > 0) {
                    f[base][i][j] += f[base][i - 2][k];
                }
            }
        }
    }
}
//数位dp
ll dp(int n) {
    //如果为0的话，直接退出即可，0无论在什么进制下都是回文串
    if (!n) {
        ll s = 0;
        for (int k = l; k <= r; k++) {
            s += k;
        }
        return s;
    }
    //记录答案
    ll res = 0;
    //枚举进制
    for (int k = l; k <= r; k++) {
        vector<int> nums;
        int nn = n;
        nums = base(nn, k);  //获得进制转换完后的数
        ll s = 0;            //存有多少个回文串
        //从最高位开始枚举，t代表最高位对应的那个最低位
        //每次确定一个高位，其实相应的低位也确定了
        for (int i = nums.size() - 1, t = 0; t <= i; i--, t++) {
            int x = nums[i];  //记录这一位的数
            //如果是这个数的最高位的话，从1开始枚举，否则从0开始枚举
            //最高位为0的情况，在下面单独枚举
            for (int j = i == nums.size() - 1; j < x;
                 j++) {  //数位dp中那课树的左子树
                int idx = nums.size() - t * 2;  // t也代表已经填完了几个高位
                s += f[k][idx][j];
            }
            //最后一个右节点的特判
            //跑一下看是否有一个高位的数小于对应的低位的，如果有的话，那我这里
            //就可以填本身，如果在发现小于之前，发现了一个大于，那么是不可以填本身的
            //如果没有小于也没有大于，说明这个数本身就是回文串，也可以++
            if (fabs(i - t) <= 1) {
                int p = i, q = t;  //从i和t开始跑，因为高位那边肯定是填本身的
                //那么就要找一个最高的位，让它来和它对应的高位去做判断，所以要挑高的低位
                int ff = 1;
                while (p <= nums.size() - 1 && t >= 0) {
                    if (nums[p] > nums[q]) {
                        ff = 0;
                        break;
                    } else if (nums[p] < nums[q])
                        break;
                    p++, q--;
                }
                if (ff == 1) s++;  //可以填本身的话就++
            }
        }
        //暴力枚举位数被nums.size()小的情况，因为位数比它小，所以数一定比它小，
        //所以位数比它小的所有情况都满足，直接暴力枚举比它小的位数，并且这个位数对应的
        //所有最高位的情况，当然不包括最高位为0的情况，0的情况在下面单独加
        for (int i = nums.size() - 1; i > 0; i--) {
            for (int j = 1; j < k; j++) {
                s += f[k][i][j];
            }
        }
        s++;  // 把0的情况再加上
              // 回文串就加k, 否则 + 1, 因为0也算到里面了, 所以是n + 1个数
        res += (s * k + (n + 1 - s));
    }
    return res;
}
signed main() {
    //预处理好每个进制
    for (int i = 2; i <= 36; i++) {
        init(i, 33);
    }
    int T;
    int Case = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &L, &R, &l, &r);
        printf("Case #%d: ", Case++);
        //询问[L,R]区间，其实就是[0,R]-[0,L-1]
        printf("%lld\n", dp(R) - dp(L - 1));
    }
    return 0;
}