D. Mr. Panda and Geometric Sequence
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 geometric sequence is a sequence of at least 3 positive integer numbers a0, a1, ..., an - 1, also there is a positive number D (D > 1) that for each i(0 ≤ i < n - 1), ai × D = ai + 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.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains one line which consists of two numbers L and R.

  • 1 ≤ T ≤ 2 × 105.
  • 0 ≤ L ≤ R ≤ 1015.
Output

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.

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

In the first test case, the only Happy Number between 123 and 124 is 124, in which 1 × 2 = 2 and 2 × 2 = 4.

In the second test case, the only Happy Number is 248.

In the third test case, the only Happy Number is 469, the common radio is .

In the fourth test case, the only Happy number between 124816 and 124832 is 124816, in which 1 × 2 = 2, 2 × 2 = 4, 4 × 2 = 8 and 8 × 2 = 16.