3473. Mr. Panda and Geometric Sequence

单点时限: 3.0 sec

内存限制: 512 MB

Mr. Panda likes playing with numbers. One day he picked up a number 3612 and found it’s interesting. 3612 can be divided into 3 numbers 3, 6 and 12 which forms an integer geometric sequence.

An integer geometirc sequence is a sequence of at least 3 positive integer numbers $a_0, a_1, \ldots, a_{n-1}$, also there is a positive number $D$ ($D >1$) that for each $i$ ($0 \le i < n-1$), $a_i \cdot D =a_{i+1}$.

Mr. Panda named this kind of numbers “Happy Number”. He also announced that leading zeros are forbidden, which means there should be no extra zeros before the numbers. Now Mr. Panda would like to know how many Happy Numbers are between $L$ and $R$ inclusive.

输入格式

The first line of the input gives the number of test cases $T$ ($1 \le T \le 2 \cdot 10^5$). $T$ cases follow. Each test case contains one line which consists of two numbers $L$ and $R$ ($0 \le L \le R \le 10^{15}$).

输出格式

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of Happy Numbers between $L$ and $R$ inclusive.

样例

Input
4
123 124
468 470
248 248
124816 124832
Output
Case #1: 1
Case #2: 1
Case #3: 1
Case #4: 1

2 人解决,7 人已尝试。

3 份提交通过,共有 17 份提交。

9.5 EMB 奖励。

创建: 6 年,11 月前.

修改: 6 年,11 月前.

最后提交: 3 年,1 月前.

来源: ECL-Final 2017

题目标签