#P1225D. Power Products

    ID: 4976 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>hashingmathnumber theory*1800

Power Products

No submission language available for this problem.

Description

You are given $n$ positive integers $a_1, \ldots, a_n$, and an integer $k \geq 2$. Count the number of pairs $i, j$ such that $1 \leq i < j \leq n$, and there exists an integer $x$ such that $a_i \cdot a_j = x^k$.

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $2 \leq k \leq 100$).

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^5$).

Print a single integer — the number of suitable pairs.

Input

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $2 \leq k \leq 100$).

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^5$).

Output

Print a single integer — the number of suitable pairs.

Samples

6 3
1 3 9 8 24 1
5

Note

In the sample case, the suitable pairs are:

  • $a_1 \cdot a_4 = 8 = 2^3$;
  • $a_1 \cdot a_6 = 1 = 1^3$;
  • $a_2 \cdot a_3 = 27 = 3^3$;
  • $a_3 \cdot a_5 = 216 = 6^3$;
  • $a_4 \cdot a_6 = 8 = 2^3$.