Nguồn ảnh: vietnamnet.vn

Theo tín ngưỡng dân gian Việt Nam, ngày 23 tháng Chạp, Táo Quân (Ông Công Ông Táo) lên chầu trời để báo cáo với Ngọc Hoàng những việc tốt xấu trong năm. Mỗi nhà chuẩn bị lễ vật, thắp hương và thường thả cá chép để các Táo đi đường thủy cho kịp giờ.

Năm nay, vì sông đông, cá chép chỉ chịu được một lượng khói hương tối đa cho mỗi lượt chở. Táo Quân muốn ghé một dải nhà liên tiếp ven sông trong cùng một lượt đi, sao cho tổng khói hương không quá giới hạn.

Có ~N~ nhà đánh số từ ~1~ đến ~N~ theo đúng thứ tự ven sông. Nhà thứ ~i~ dâng một lễ vật có mã số ~A_i~.

Định nghĩa khói hương của một lễ vật là:

~\Omega(x) =~ tổng số thừa số nguyên tố của ~x~ tính cả bội số.

Trong một lượt cá chép chở Táo, tổng khói hương tối đa cho phép là ~K~.

Táo quân sẽ chọn một trong các tòa nhà ~[l..r]~ để ghé trong cùng một lượt, và hợp lệ nếu:

$$\sum_{i=l}^r \Omega(A_i) \leq K$$

Yêu cầu: đếm số lượng đoạn ~[l..r]~ hợp lệ.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \leq N \leq 2 \times 10^5, 0 \leq K \leq 10^9)~.
• dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, \dots, A_n~ ~(1 \leq A_i \leq 10^6)~.

Output

• Gồm một dòng duy nhất chứa một số nguyên là đáp án thỏa mãn yêu cầu đề bài.

Scoring

Example input 1

10 5
1 12 5 64 18 7 100 2 27 30

Example output 1

16