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 ≤ 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 ≤ 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 ≤ K ≤ 20) và N (1 ≤ N ≤ 10^18).
• Dòng thứ hai chứa K số nguyên tố phân biệt p_i (2 ≤ p_i ≤ 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ố ≤ 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ố.