Given an array ~a~ with length ~N~ of positive integers, find the amount of unordered pairs of indices ~i,j\ i \neq j~ there are such that ~a_i\cdot a_j~ is an irreducible ~K^{th}~ root.

A ~K^{th}~ root is reducible if it has a ~K^{th}~ power other than 1 as a factor.

Input Specification

The first line will contain two integers, ~N\ (1 \leq N \leq 10^5)~, and ~K\ (2 \leq K \leq 30)~.

The next line will contain ~N~ integers, the array ~a\ (2 \leq a_i \leq 10^6)~.

Output Specification

You are to output one line, the number of unordered pairs.

Subtasks

Subtask 1 [30%]

~N \leq 3\cdot 10^3~

Subtask 2 [70%]

No further constraints.

Sample Input

4 3
2 3 4 9

Sample Output

4