Divisible Sum Pairs (Divisible Sum Pairs)

Source: HackerRank

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$ and a positive integer $k$, count index pairs $(i,j)$ such that

and

Each index pair is counted once.

Input

The first line contains $n$ and $k$. The second line contains $n$ integers $a_i$.

Output

Print the number of valid pairs.

Subtask

Subtask 1 (20 points): $2\le n\le20$, $1\le k,a_i\le20$.

Subtask 2 (30 points): $2\le n\le60$, $1\le k,a_i\le100$.

Subtask 3 (50 points): $2\le n\le100$, $1\le k\le100$, $1\le a_i\le100$.

Example

Input

6 3
1 3 2 6 1 2

Output

5

Explanation

The sample follows the definitions and rules above.