Arya and Bran are playing a game. Initially, two positive integers A and B are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace A with A  k*B for any positive integer k, or replace B with B  k*A for any positive integer k. The first person to make one of the numbers drop to zero or below loses.
For example, if the numbers are initially (12, 51), the game might progress as follows:
Given four integers A_{1}, A_{2}, B_{1}, B_{2}, count how many winning positions (A, B) there are with A_{1} ≤ A ≤ A_{2} and B_{1} ≤ B ≤ B_{2}.
The first line of the input gives the number of test cases, T. T test cases follow, one per line. Each line contains the four integers A_{1}, A_{2}, B_{1}, B_{2}, separated by spaces.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of winning positions (A, B) with A_{1} ≤ A ≤ A_{2} and B_{1} ≤ B ≤ B_{2}.
1 ≤ T ≤ 100.
1 ≤ A_{1} ≤ A_{2} ≤ 1,000,000.
1 ≤ B_{1} ≤ B_{2} ≤ 1,000,000.
A_{2}  A_{1} ≤ 30.
B_{2}  B_{1} ≤ 30.
A_{2}  A_{1} ≤ 999,999.
B_{2}  B_{1} ≤ 999,999.
No additional constraints.
Input 
Output 
3

Case #1: 0

Points  Correct  Attempted 

16pt  680  1091 
25pt  244  450 