Problem C
Unlockable

You have $N$ locks that all share a common integer $a > 1$. Each lock is associated with its own integer $b_i$. A key can be described by a pair of positive integers $(x,y)$, and it will unlock a lock with $b_i$ if it satisfies $ya^x = b_i$.

Find all possible keys $(x,y)$ such that $ya^x = b_i$ for at least one $b_i$.

Input

The first line contains two integers $N$ and $a$ ($1 \leq N \leq 2 \cdot 10^5$, $1 < a \leq 10^9$), the number of locks and the common integer $a$.

The second line contains $N$ integers $b_1, b_2, \dots , b_N$ $(1 \leq b_i \leq 10^9)$, where $b_i$ denotes the integer that describes the $i$-th lock.

Output

Print an integer: the number of pairs of positive integers $(x,y)$ that satisfies $ya^x = b_i$ for at least one $i$ $(1\leq i \leq N)$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

1 2
8

3

5 3
2 4 6 9 15

4

3 6
2 4 24

1

6 9
9 18 27 9 18 81

5