题目描述

哥萨克·乌斯研究了一种很有趣的操作：把一个数乘以它的任意一个约数。例如，对于数字 $6$，他可以把它乘以 $1$、$2$、$3$ 或 $6$，分别得到 $6$、$12$、$18$ 或 $36$。

接着，他学会了把这种操作用于一个由 $n$ 个数组成的数组 $a$。执行一次操作时，他会把数组中每个数 $a_i$ 都乘以 $a_i$ 的任意一个约数。乌斯把这个操作命名为“数组补乘”。

随后，乌斯称一对数 $(l,r)$ 是“好的”，如果满足以下条件：

• $1\le l\le r\le n$；
• 可以执行不超过 $k$ 次“数组补乘”，使得 $a_l,a_{l+1},\ldots,a_r$ 全部变得相等。

你的任务是：给定数组，求“好的”数对数量。

最近哥萨克发现，数组中所有数的质因子都小于 $30$。回忆一下，质数是恰好有两个不同正约数的自然数。

输入格式

第一行包含三个整数 $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,\ldots,a_n$（$1\le a_i\le 10^6$），表示数组 $a$ 的元素。保证不存在一个数能被大于 $30$ 的质数整除。

输出格式

输出一个整数，表示“好的”数对数量。

输入

5 1 0
6 18 12 24 54

输出

9

数据范围与评分

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$。