Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Power Products

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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$$$.

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.

Example

Input

6 3 1 3 9 8 24 1

Output

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 03:57:09 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|