Bi được giao nhiệm vụ đo tốc độ bơm của hai máy bơm nước. Để làm như vậy, cô ấy đã sử dụng máy bơm để bơm nước vào bể chứa nước và kiểm tra lượng nước đã được bơm vào bể trong một thời gian cụ thể. Bi phát hiện ra rằng máy bơm thứ nhất bơm được ~a~ lít nước trong ~b~ giây và máy bơm thứ hai bơm được ~c~ lít nước nước trong ~d~ giây. Nếu khi cả hai máy bơm được sử dụng cùng một lúc, chúng cùng nhau bơm được ~b~ lít nước trong ~d~ giây. Thật không may, Bi đã làm đổ nước vào cuốn sổ ghi các giá trị trên và không thể khôi phục các giá trị ~a~ và ~c~. Tuy nhiên, cô ấy nhớ rằng những giá trị này là số nguyên dương.

Hãy lập trình giúp Bi xem có bao nhiêu cách để chọn các giá trị ~a~ và ~c~ đã bị mất đi.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số testcase thỏa ~1\le T\le \le 1000~.

~T~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~b, d~ thỏa ~1 \le b, d \le 10^9~.

Output

Ứng với mỗi testcase in ra số cách cần tìm.

Samples

Sample Input 1

3
9 6
40 60
60 40

Sample Output 1

4
13
29

Note

Ở testcase ~1~ các phương án chọn là ~a = 3, c = 7; a = 6, c = 5; a = 9, c = 3;a = 12, c = 1~.