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

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\).

Input

• 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})\).

Output

• 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.

Example

2
15 2 3 5
30 2 4 9

21
44