Given two integers A and B. Sequence S is defined as follow:
• S0 = A
• S1 = B
• Si = |Si-1 - Si-2| for i ≥ 2
Count the number of distinct numbers in S .
LastDefence
Input
The first line of the input gives the number of test cases, T. T test cases follow. T is about 100000.
Each test case consists of one line - two space-separated integers A, B. (0 ≤ A， B ≤ 10^18).
Each test case consists of one line - two space-separated integers A, B. (0 ≤ A， B ≤ 10^18).
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 distinct numbers in S .
Sample Input
2
7 4
3 5
Sample Output
Case #1: 6
Case #2: 5