J. Unnamed numbers
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Vilmantas is a real numberphile. He is fascinated by numbers, but most of all he likes numbers, which are named after famous scientist and mathematicians. For example, there are Mersenne primes (MP = 2p - 1, where p is prime), Graham's number (extremely large number, no way to define it here in commonly known notation).

Vilmantas would love to have numbers named after him. This is what he came up with. He takes some positive number and extracts every 2-digit number in the given order. For example, if we extract number 10324, we get a sequence of S = {10, 03, 32, 24}. Then he checks for three conditions:

  1. S is not empty;
  2. Every number Si must be not prime;
  3. Every neighboring numbers in S must be coprime (in other words, for every 1 ≤ i ≤ |S| - 1 greatest common divisor GCD(Si, Si + 1) must be equal to 1);

The previous number 10324 breaks two of the conditions: 3 is prime and while GCD(10, 3) = GCD(3, 32) = 1, 32 and 24 are not coprime (GCD(32, 24) = 8).

If some number satisfies all three of the conditions, then it is called Vilmantas' number.

Given numbers a and b, count the Vilmantas' numbers in range [a;b].

Input

The first line contains the number of test cases T (T ≤ 10). In the following T lines there are integers a and b (1 ≤ a ≤ b ≤ 1011).

Output

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the count of Vilmantas' numbers from a to b inclusive.

Examples
Input
4
1 9
23 23
25 25
100 200
Output
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 11
Note

Only integers coprime to zero are 1 and  - 1.