Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

D. Power Products
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given n positive integers a1,,an, and an integer k2. Count the number of pairs i,j such that 1i<jn, and there exists an integer x such that aiaj=xk.

Input

The first line contains two integers n and k (2n105, 2k100).

The second line contains n integers a1,,an (1ai105).

Output

Print a single integer — the number of suitable pairs.

Example
Input
6 3
1 3 9 8 24 1
Output
5
Note

In the sample case, the suitable pairs are:

  • a1a4=8=23;
  • a1a6=1=13;
  • a2a3=27=33;
  • a3a5=216=63;
  • a4a6=8=23.