nguyên lý bù trừ (dễ)

Hôm nay lớp \(X\) có một buổi kiểm tra và tất cả thành viên trong lớp phải làm một bài kiểm tra gồm có 3 bài toán.

Sau khi kiểm tra xong, thầy giáo chủ nhiệm lớp \(X\) đã báo cáo với thầy \(Y\) - Tổ trưởng bộ môn Toán rằng: Trong lớp có:

• \(u_1\) em giải được bài toán \(I\),

• \(u_2\) em giải được bài toán \(II\),

• \(u_3\) em giải được bài toán \(III\),

• \(u_4\) em giải được bài toán \(II\) và \(III\),

• \(u_5\) em giải được bài toán \(I\) và \(II\),

• \(u_6\) em giải được bài toán \(I\) và \(III\),

• \(u_7\) em giải được cả ba bài.

Vì thầy \(Y\) hơi nghi ngờ về kết quả của thầy giáo chủ nhiệm lớp \(X\) nên thầy \(Y\) muốn lên đầy nhờ các bạn kiểm tra xem, kết quả mà thầy giáo chủ nhiệm lớp \(X\) đã báo cáo là đúng hay là sai ? Nếu đúng thì hãy in ra số lượng thành viên của lớp \(X\), còn nếu sai thì in ra \(-1\).

Input:

• Dòng thứ nhất chứa số \(t\) \((1\le t\le 1000)\) - Thể hiện số testcase.

• \(t\) block tiếp theo, mỗi block gồm \(7\) số nguyên dương \(u_1,u_2,u_3,u_4,u_5,u_6,u_7\) \((1\le u_i\le 200000)\), mỗi số viết một dòng.

Output:

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

1
20
14
10
5
2
6
1

32

Cho ba số \(a, b, c\). Hãy đếm số lượng số nguyên dương không lớn hơn \(n\) sao cho số đó chia hết cho một trong ba số \(a, b, c\).

Input

• Gồm một dòng duy nhất chứa bốn số lần lượt là \(n, a, b\) và \(c\) \((1 \leq a, b, c \leq n \leq 10^{12})\).

Output

• Gồm một số duy nhất số lượng số thỏa mãn đề.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Bạn được cho \(k\) số nguyên tố phân biệt \(a_1, a_2, \ldots, a_k\) và một số nguyên \(n\).

Nhiệm vụ của bạn là tính toán có bao nhiêu trong \(n\) số nguyên dương đầu tiên chia hết cho ít nhất một trong các số nguyên tố đã cho.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\)
• Dòng thứ hai có \(k\) số nguyên tố \(a_1, a_2, \ldots, a_k\)

Constraints

• \(1 \leq n \leq 10^{18}\)
• \(1 \leq k \leq 20\)
• \(2 \leq a_i \leq n\)

Output

• In một số nguyên: số lượng số nguyên trong khoảng \(1, 2, \ldots, n\) chia hết cho ít nhất một trong các số nguyên tố.

Example

20 2
2 5

12

Cho một danh sách \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số cặp số nguyên mà nguyên tố cùng nhau (tức là, ước số chung lớn nhất của chúng là một).

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng phần tử
• Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2, ..., x_n\): nội dung của danh sách

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq x_i \leq 10^6\)

Output

• In một số nguyên: câu trả lời cho nhiệm vụ

Example

8
5 4 20 1 16 17 5 15

19