Cho bốn số nguyên dương \(n, a, b, c\) hãy tính tổng sau:

\[ \sum \left\lfloor \dfrac{n}{x} \right\rfloor \]

Với \(x\) là số nguyên thỏa mãn các tính chất sau:

• \(x\) chia hết cho \(a\) hoặc \(x\) chia hết cho \(b\) hoặc \(x\) chia hết cho cả \(a\) và \(b\)
• \(x\) không chia hết cho \(c\).
• Trong đó \(\left\lfloor x \right\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên dương \(q\) \((1 \leq q \leq 50)\) là số bộ thử nghiệm.
• \(q\) dòng tiếp theo, dòng thứ \(i\) tương ứng với bộ thử nghiệm thứ \(i\), dòng thứ \(i\) chứa bốn số nguyên \(n, a, b, c\) \((1 \leq n, a, b, c \leq 10^{9})\).

Dữ liệu ra

In ra \(q\) dòng, dòng thứ \(i\) chứa kết quả tương ứng với bộ thử nghiệm thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(30\%\) số điểm): \(a = b\) và \(c > n\).
• Subtask \(3\) (\(20\%\) số điểm): \(c > n\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Input 1

2
15 2 3 5
30 2 4 9

Output 1

21
44

Note

• Trong bộ thử nghiệm đầu tiên, các giá trị \(x\) thỏa mãn là \(2, 3, 4, 6, 8, 9, 12, 14\).
• Vì vậy \(\sum \left\lfloor \dfrac{n}{x} \right\rfloor = 7 + 5 + 3 + 2 + 1 + 1 + 1 + 1 = 21\)