숫자 게임

Arya와 Bran은 게임을 하고 있다. 처음에는 두 양의 정수 A와 B가 칠판에 적혀 있다. Arya부터 시작하여 두 사람이 번갈아 차례를 진행한다. 자신의 차례에 플레이어는 임의의 양의 정수 k에 대해 A를 A - kB로 바꾸거나, 임의의 양의 정수 k에 대해 B를 B - kA로 바꿀 수 있다. 두 수 중 하나를 영 이하로 만든 첫 번째 사람이 패배한다.

예를 들어, 처음 두 수가 (12, 51)라면 게임은 다음과 같이 진행될 수 있다.

• Arya는 51을 51 - 3*12 = 15으로 바꾸어 칠판에 (12, 15)를 남긴다.

• Bran은 15을 15 - 1*12 = 3으로 바꾸어 칠판에 (12, 3)를 남긴다.

• Arya는 12을 12 - 3*3 = 3으로 바꾸어 칠판에 (3, 3)를 남긴다.

• Bran은 하나의 3을 3 - 1*3 = 0으로 바꾸고 패배한다. 칠판에 (A, B)가 적힌 상태로 시작하는 게임에서 Bran이 무엇을 하든 Arya가 항상 이길 수 있다면, (A, B)를 승리 상태라고 한다.

네 정수 $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$이 주어질 때, $A_{1}$ ≤ A ≤ $A_{2}$이고 $B_{1}$ ≤ B ≤ $B_{2}$인 승리 상태 (A, B)의 수를 센다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $A_{1}$ ≤ $A_{2}$ ≤ 1,000,000. 1 ≤ $B_{1}$ ≤ $B_{2}$ ≤ 1,000,000.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. $A_{2}$ - $A_{1}$ ≤ 30. $B_{2}$ - $B_{1}$ ≤ 30.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 90초. $A_{2}$ - $A_{1}$ ≤ 999,999. $B_{2}$ - $B_{1}$ ≤ 999,999.

추가 제약 조건은 없다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 네 정수 $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 $A_{1}$ ≤ A ≤ $A_{2}$이고 $B_{1}$ ≤ B ≤ $B_{2}$인 승리 상태 (A, B)의 수이다.