숫자 게임

아리아와 브랜이 게임을 한다. 처음에 칠판에는 양의 정수 $A$와 $B$가 적혀 있다. 아리아부터 번갈아 차례를 진행한다. 차례가 된 플레이어는 양의 정수 $k$를 하나 골라 $A$를 $A - k \times B$로 바꾸거나, $B$를 $B - k \times A$로 바꿀 수 있다. 두 수 가운데 하나를 0 이하로 만든 사람이 진다.

처음 수가 $(12, 51)$이면 게임은 예를 들어 다음처럼 흘러간다.

• 아리아가 51을 $51 - 3 \times 12 = 15$로 바꾼다. 칠판에는 $(12, 15)$가 남는다.
• 브랜이 15를 $15 - 1 \times 12 = 3$으로 바꾼다. 칠판에는 $(12, 3)$이 남는다.
• 아리아가 12를 $12 - 3 \times 3 = 3$으로 바꾼다. 칠판에는 $(3, 3)$이 남는다.
• 브랜이 3 하나를 $3 - 1 \times 3 = 0$으로 바꾸고, 진다.

브랜이 어떻게 두더라도 아리아가 반드시 이기면 $(A, B)$를 승리 위치라고 부른다.

정수 $A_1$, $A_2$, $B_1$, $B_2$가 주어진다. $A_1 \le A \le A_2$이고 $B_1 \le B \le B_2$인 승리 위치 $(A, B)$의 개수를 세어라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 정수 $A_1$, $A_2$, $B_1$, $B_2$가 공백으로 구분되어 있다.

제한

• $1 \le T \le 100$
• $1 \le A_1 \le A_2 \le 10^6$
• $1 \le B_1 \le B_2 \le 10^6$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $A_1 \le A \le A_2$이고 $B_1 \le B \le B_2$인 승리 위치 $(A, B)$의 개수이다.