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

Козак Вус досліджував дуже цікаву операцію: домноження числа на будь-який дільник. Наприклад, число $6$ він може домножити на $1$, $2$, $3$ або $6$ і отримати $6$, $12$, $18$ або $36$ відповідно.

Далі він навчився робити таку операцію з масивом чисел $a$, який складається з $n$ чисел. Для цього він просто кожне число масиву $a_i$ множить на будь-який дільник $a_i$. Винайдену операцію він назвав «домноження масиву».

Одразу після цього Вус вирішив називати пару чисел $(l,r)$ «гарною», якщо виконуються наступні умови:

• $1\le l\le r\le n$.

• Можна виконати не більше $k$ «домножень масиву» таким чином, щоб усі числа $a_l,a_{l+1},...,a_r$ стали однаковими.

Ваша ж задача "— для заданого масиву знайти кількість «гарних» пар чисел. Нещодавно Козак з'ясував, що всі прості дільники чисел з масиву менші за $30$. Нагадаємо, що простим називається натуральне число, яке має рівно два різних натуральних дільники.

Input

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

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

Output

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

Examples

Note

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

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

Пари $(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$.

Scoring

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

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

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

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

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

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

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

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

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

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

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

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