The Resonance Equation - Repovive Starter Round 5 | Repovive

17E. The Resonance Equation

2500 pts1s256 MB

You are given an array $a$ of $n$ integers and an integer $x$ .

You need to find the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$ and the following equation holds true:

\begin{aligned} \operatorname{lcm}(a_i, a_j) - \gcd(a_i, a_j) = x \end{aligned}

where $\operatorname{lcm}(a_i, a_j)$ denotes the least common multiple of $a_i$ and $a_j$ , and $\gcd(a_i, a_j)$ denotes their greatest common divisor.

Input

The first line contains two integers $n$ and $x$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le x \le 10^9$ ) - the size of the array and the target value.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) - the elements of the array $a$ .

Output

Print a single integer — the number of valid pairs $(i, j)$ that satisfy the given equation.

Samples

Input

6 5
1 2 3 5 6 10

Explanation

In the given example, $x = 5$ and $a = [1, 2, 3, 5, 6, 10]$ .

There are exactly $3$ valid pairs of indices $(i, j)$ :

$i = 1, j = 5$ ( $a_1 = 1, a_5 = 6$ ): $\operatorname{lcm}(1, 6) - \gcd(1, 6) = 6 - 1 = 5$ .
$i = 2, j = 3$ ( $a_2 = 2, a_3 = 3$ ): $\operatorname{lcm}(2, 3) - \gcd(2, 3) = 6 - 1 = 5$ .
$i = 4, j = 6$ ( $a_4 = 5, a_6 = 10$ ): $\operatorname{lcm}(5, 10) - \gcd(5, 10) = 10 - 5 = 5$ .

All other pairs yield a difference other than $5$ .

Output

You are given an array $a$ of $n$ integers and an integer $x$ .

You need to find the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$ and the following equation holds true:

\begin{aligned} \operatorname{lcm}(a_i, a_j) - \gcd(a_i, a_j) = x \end{aligned}

where $\operatorname{lcm}(a_i, a_j)$ denotes the least common multiple of $a_i$ and $a_j$ , and $\gcd(a_i, a_j)$ denotes their greatest common divisor.

The first line contains two integers $n$ and $x$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le x \le 10^9$ ) - the size of the array and the target value.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) - the elements of the array $a$ .

Print a single integer — the number of valid pairs $(i, j)$ that satisfy the given equation.

In the given example, $x = 5$ and $a = [1, 2, 3, 5, 6, 10]$ .

There are exactly $3$ valid pairs of indices $(i, j)$ :

$i = 1, j = 5$ ( $a_1 = 1, a_5 = 6$ ): $\operatorname{lcm}(1, 6) - \gcd(1, 6) = 6 - 1 = 5$ .
$i = 2, j = 3$ ( $a_2 = 2, a_3 = 3$ ): $\operatorname{lcm}(2, 3) - \gcd(2, 3) = 6 - 1 = 5$ .
$i = 4, j = 6$ ( $a_4 = 5, a_6 = 10$ ): $\operatorname{lcm}(5, 10) - \gcd(5, 10) = 10 - 5 = 5$ .

All other pairs yield a difference other than $5$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

17E. The Resonance Equation

Input

Output

Samples

17E. The Resonance Equation

Input

Output

Samples