수 게임 (작은 입력)

아리아와 브랜이 게임을 한다. 처음에 칠판에는 양의 정수 $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 1{,}000{,}000$
• $1 \le B_1 \le B_2 \le 1{,}000{,}000$
• $A_2 - A_1 \le 30$
• $B_2 - B_1 \le 30$

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