Arya và Bran chơi với hai số nguyên dương \(A,B\) trên bảng, Arya đi trước. Mỗi lượt, người chơi thay \(A\) bằng \(A-kB\), hoặc \(B\) bằng \(B-kA\), với số nguyên dương \(k\). Người đầu tiên làm một số giảm xuống 0 hoặc âm sẽ thua.

Ví dụ từ \((12,51)\): Arya đổi 51 thành \(51-3\cdot12=15\); Bran đổi 15 thành 3; Arya đổi 12 thành 3; Bran buộc đổi một số 3 thành 0 và thua.

Gọi \((A,B)\) là thế thắng nếu Arya có thể chắc chắn thắng bất kể Bran chơi thế nào. Cho \(A_1,A_2,B_1,B_2\), hãy đếm số thế thắng với \(A_1\le A\le A_2\) và \(B_1\le B\le B_2\).

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm bốn số \(A_1,A_2,B_1,B_2\).

Dữ liệu ra

In Case #x: y, với \(y\) là số thế thắng trong hình chữ nhật đã cho.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_1\le A_2\le10^6\), \(1\le B_1\le B_2\le10^6\).
• Bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(A_2-A_1\le30\), \(B_2-B_1\le30\).
• Lớn: các hiệu không quá 999999.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
5 5 8 8
11 11 2 2
1 6 1 6

Case #1: 0
Case #2: 1
Case #3: 20

Nguồn

Google Code Jam 2010, Vòng 1A, bài Number Game.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.