Tiến sĩ Hanks là một chuyên gia nổi tiếng trong lĩnh vực công nghệ sinh học (Bio-Tech), và con trai ông tên là Hankson. Vừa tan học trở về, Hankson đang suy nghĩ về một bài toán thú vị.

Hôm nay trong lớp, giáo viên đã giảng về cách tìm ước số chung lớn nhất (GCD) và bội số chung nhỏ nhất (LCM) của hai số nguyên dương \(c_1\) và \(c_2\). Giờ đây Hankson nghĩ rằng mình đã hiểu rõ phần này, và bắt đầu suy nghĩ về một "bài toán ngược" của GCD và LCM. Cụ thể:

Cho bốn số nguyên dương \(a_0, a_1, b_0, b_1\), hãy tìm số lượng số nguyên dương \(x\) thỏa mãn tất cả các điều kiện sau:

1. \(\gcd(x, a_0) = a_1\)
2. \(\text{lcm}(x, b_0) = b_1\)

Tuy nhiên, Hankson nhanh chóng nhận ra có thể có nhiều giá trị \(x\) thỏa mãn, thậm chí không có giá trị nào. Nên thay vì tìm từng \(x\), cậu muốn biết có bao nhiêu giá trị x thỏa các điều kiện đó.

Bạn hãy giúp cậu ấy viết chương trình để đếm số lượng giá trị \(x\) thỏa mãn.

Định dạng vào

• Dòng đầu tiên là một số nguyên \(n\), là số bộ dữ liệu.
• Tiếp theo là \(n\) dòng, mỗi dòng gồm bốn số nguyên dương \(a_0, a_1, b_0, b_1\), cách nhau bởi dấu cách.

Dữ liệu đảm bảo: \(a_0\) chia hết cho \(a_1\), và \(b_1\) chia hết cho \(b_0\).

Định dạng ra

• Gồm \(n\) dòng, mỗi dòng là kết quả ứng với một bộ dữ liệu: số lượng số nguyên dương \(x\) thỏa cả hai điều kiện.
• Nếu không có giá trị \(x\) nào thỏa mãn, in ra 0.

Input 1

2 
41 1 96 288 
95 1 37 1776

Output 1

6 
2

Giải thích

Dữ liệu 1: Các giá trị thỏa mãn là \(9,18,36,72,144,288\), tổng cộng có 6 giá trị.

Dữ liệu 2: Các giá trị thỏa mãn là \(48,1776\), có 2 giá trị.

Ràng buộc dữ liệu

• Với 50% số test:
  • \(1 \leq a_0,a_1,b_0,b_1 \leq 10000\)
  • \(n \leq 100\)
• Với toàn bộ dữ liệu:
  • \(1 \leq a_0,a_1,b_0,b_1 \leq 2 \times 10^9\)
  • \(n \leq 2000\)