Женя и Саша вместе играют в хоккей. Тренировки проходят $$$n$$$ раз в неделю в дни $$$a_1, a_2, \ldots, a_n$$$. В каждой неделе ровно $$$d$$$ дней, а в одном году ровно $$$w$$$ недель, дни нумеруются с единицы. Саша посещает каждую тренировку, а Женя приходит на тренировку, если номер дня в году является простым числом и в этот день есть тренировка. Сколько тренировок друзья посетят вместе в течение года?
Если вы решаете задачу на языке Python, рекомендуем отправлять решения на PyPy.
В первой строке содержатся три целых числа $$$n$$$, $$$d$$$ и $$$w$$$ $$$(1 \le n \le d \le 10^6$$$, $$$1 \le w \le 10^7)$$$ — количество тренировок в неделю, количество дней в неделе и количество недель в году.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_1 \lt a_2 \lt \ldots \lt a_n \le d)$$$ — дни недели, когда проводятся тренировки.
Гарантируется, что $$$d \cdot w$$$ не превышает $$$10^7$$$.
В единственной строке выведите одно целое число — количество тренировок, которые Женя и Саша посетят вместе в течение года.
2 7 43 7
3
В примере из условия стандартное количество дней в неделе. Тренировки проходят по средам(3) и воскресеньям(7), эти числа являются простыми, кроме того, простым является число $$$17$$$, которое выпадает на среду третьей недели.