Козак Вус і домноження

Вхідні дані

Перший рядок містить три цілі числа $n$, $k$ та $g$ (1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 100, 0 \leq g \leq 12) "— кількість елементів в масиві, максимальна кількість операцій «домноження масиву» та номер блоку, до якого належить тест відповідно.

Другий рядок містить $n$ цілих чисел a_1, a_2,..., a_n (1 \leq a_i \leq 10^6) "— елементи масиву $a$. Гарантується, що немає такого числа, яке ділиться на просте число більше за $30$.

Вихідні дані

Виведіть одне число "— кількість «гарних» пар.

Приклади

Примітка

Пояснення до першого прикладу:

Розглянемо всі «гарні» пари:

Пари $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$ та $(5,5)$ «гарні» навіть без «домножень масиву».

• $(1,2)$: a_1 домножуємо на $3$, а a_2 на $1$.

• $(1,3)$: a_1 домножуємо на $6$, a_2 на $2$, а a_3 на $3$.

• $(2,3)$: a_2 домножуємо на $2$, а a_3 на $3$.

• $(3,4)$: a_3 домножуємо на $4$, а a_4 на $2$.

Оцінювання

1. ($6$ балів) n \leq 10^3, k = 0.

2. ($6$ балів) n \leq 2 \cdot 10^5, k = 0.

3. ($8$ балів) n \leq 10^2, k = 100.

4. ($6$ балів) n \leq 10^3, k = 100.

5. ($6$ балів) n \leq 2 \cdot 10^5, k = 100.

6. ($8$ балів) n \leq 10^3, усі a_i = 2^{m_i}, де m_i — невід'ємне ціле число.

7. ($7$ балів) n \leq 2 \cdot 10^5, усі a_i = 2^{m_i}, де m_i — невід'ємне ціле число.

8. ($5$ балів) n \leq 10^3, усі a_i = 2^{m_i}\cdot3^{l_i}, де m_i та l_i — невід'ємні цілі числа.

9. ($10$ балів) n \leq 2 \cdot 10^5, усі a_i = 2^{m_i}\cdot3^{l_i}, де m_i та l_i — невід'ємні цілі числа.

10. ($10$ балів) n \leq 10^2.

11. ($11$ балів) n \leq 10^3.

12. ($17$ балів) n \leq 2 \cdot 10^5.