U165599 「HDU 6156」Palindrome Function

$\text{From:}$ [HDU 6156](http://acm.hdu.edu.cn/showproblem.php?pid=6156) 题解推销：[cnblogs](https://www.cnblogs.com/cyl06/p/HDU6156.html)

我们知道，当一个数从前往后和从后往前读一样时，这个数就是回文数，例如 $666$ 和 $747$。有的数在十进制下不是回文数，但它们在其他进制中可能是回文数。例如 $288$，它在十进制下不是一个回文数。但如果我们把它转为 $17$ 进制下的数，就是 $\text{GG}$，就成为了一个回文数。 所以我们定义一个有趣的函数 $f(n,k)$： 如果 $n$ 在 $k$ 进制下是回文数，$f(n,k)=k$，否则 $f(n,k)=1$。 现在给出 $4$ 个整数 $L,R,l,r$，你需要计算 $\sum\limits_{i=L}^R\sum\limits_{j=l}^r f(i,j)$ 的值。 注意：当表示一个 $k$ 进制的数且 $k>10$ 时，我们需要用 $\text{A}$ 代替 $10$，用 $\text{B}$ 代替 $11$， $\text{C}$ 代替 $12$，以此类推。最大的是 $\text{Z}(35)$，所以我们只讨论最多 $36$ 进制下的情况。

第一行包含一个整数 $T$，表示测试用例的个数。 接下来 $T$ 行，每行包含 $4$ 个整数 $L,R,l,r$。

对于每组测试用例，以 `Case #i: ans` 的方式输出，并用换行隔开。

对于 $100\%$ 的数据，$1\le T\le 10^5,1\le L\le R\le 10^9,2\le l\le r\le 36$。 $\text{Translated by cyl06.}$