401578: GYM100495 J Unnamed numbers

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 (M_P = 2^p - 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 S_i 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(S_i, S_i + 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].

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 ≤ 10¹¹).

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.

4
1 9
23 23
25 25
100 200

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 11

Only integers coprime to zero are 1 and  - 1.