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.
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.
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.
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.
## 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.
[samples]
## 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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of nodes, $ m \in \mathbb{Z} $ the number of edges, and $ k \in \mathbb{Z} $ the number of important nodes.
- Let $ G = (V, E) $ be an undirected connected graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, where each edge $ (u, v) \in E $ has weight $ c_{u,v} \geq 0 $.
- Let $ I \subseteq V $ be the set of important nodes, with $ |I| = k $.
**Constraints**
1. $ 1 \leq T \leq 150 $
2. $ 2 \leq n \leq 15 $, $ 1 \leq k \leq n $, $ 1 \leq m \leq \binom{n}{2} $
3. Edge weights satisfy $ 0 \leq c_{u,v} \leq 10^6 $
4. Graph is connected, no self-loops, no multiple edges.
**Objective**
For each test case, find the minimum total weight of a connected subgraph $ H = (V_H, E_H) $ of $ G $ such that $ I \subseteq V_H $.
That is, compute:
$$
\min_{\substack{H \subseteq G \\ I \subseteq V_H \\ H \text{ connected}}} \sum_{(u,v) \in E_H} c_{u,v}
$$