Cho tập hợp P gồm K số nguyên tố phân biệt và số nguyên dương N. Hãy đếm số lượng số nguyên dương \(\le N\) chia hết cho ít nhất một số trong tập P.

Sử dụng nguyên lý bù trừ (inclusion–exclusion principle):

• Với \(K \le 20\), duyệt tất cả \(2^K\) tập con của P.
• Với mỗi tập con, tính LCM của các phần tử. Số lượng bội số của LCM trong [1, N] là N / LCM.
• Cộng nếu tập con lẻ, trừ nếu tập con chẵn.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên K (\(1 \le K \le 20\)) và N (\(1 \le N \le 10^18\)).
• Dòng thứ hai chứa K số nguyên tố phân biệt \(p_i\) (\(2 \le p_i \le 10^9\)).

Đầu ra

Một số nguyên duy nhất là kết quả.

Ví dụ

Input:
3 30
2 3 5

Output:
22

Giải thích

Số \(\le 30\) chia hết cho 2, 3 hoặc 5: 2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30 → 22 số.

Ràng buộc & Subtasks