给定一个长度为 $n$ 的正整数数列 $a_1,a_2,…,a_n$ 和一个正整数 $k$。

请你判断共有多少个数对 $(l,r)$ 同时满足：

• $1 \le l < r \le n$
• 存在一个整数 $x$ 使得 $a_l \times a_r = x^k$ 成立

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个正整数 $a_1,a_2,…,a_n$。

输出格式

一个整数，表示满足条件的数对的数量。

数据范围

前三个测试点满足 $2 \le n \le 10$。
所有测试点满足 $2 \le n \le 10^5$，$2 \le k \le 100$，$1 \le a_i \le 10^5$。

输入样例：

6 3
1 3 9 8 24 1

输出样例：

5