Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Repeating Units

Limits: 1s, 512 MB

A number is called repunit (Repeating Units) if the number is made of only 1’s, uch as 1,11 or 11111111. Experimenting repunit numbers is a great game if you can find out the divisibility property. Today, you are assigned with a similar task.

Given two integers A and B, you have to find out how many numbers between A and B (inclusive) can divide at least one repunit number.

Input

First line takes an integer T, the number of test cases. Next T lines takes two integers A and B.

  • 1 ≤T ≤1000
  • 1 ≤ A, B ≤ 1015

Output

For each test case, print the case number and the desired output.

Samples

InputOutput
2
3 6
1 7
Case 1: 1
Case 2: 3

Between 1 to 7, there are 3 such numbers - 1,3 and 7. 1 divides 1, 3 divides 111 and 7 divides 1,11,111.

Discussion