Problem Background

Enzyme runs through the Ringed Genesis, just like a Rabbit runs through a Ring.

Problem Description

There is a long ring formed by $n$ grids connected end to end, numbered from $0$ to $n-1$.

There is also an animal—a rabbit. The rabbit's step length is $k$. If the rabbit is currently in the $i$-th grid, then the next second it will jump to the $(i+k) \bmod n$-th grid.

Now there are $m$ rabbits, and the initial grid of the $i$-th rabbit is the $p_i$-th grid. As time passes, some grids are passed by the rabbits, while others are never passed by the rabbits.

You need to find out how many grids will never be passed by any rabbit.

Input Format

Read data from standard input.

The first line contains three positive integers $n, m, k$, representing the length of the ring, the number of rabbits, and the step length, respectively.

The second line contains $m$ non-negative integers $p_1, p_2, \dots, p_m$, representing the initial grids of the rabbits.

Output Format

Output data to standard output.

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

4 2 2
0 1

Sample Output #1

0

Sample Input #2

4 2 2
0 2

Sample Output #2

2

Notes

Subtask 1 ($10\%$): $k=1$.

Subtask 2 ($20\%$): $k$ divides $n$, i.e., $\gcd(k, n) = k$.

Subtask 3 ($25\%$): $1 \leq n \leq 1000$, $1 \leq m \leq 1000$.

Subtask 4 ($45\%$): No special restrictions.

For all data, $1 \leq n \leq 10^6$, $1 \leq m \leq 10^6$, $1 \leq k \leq n$.

见题面 Input 部分

见题面 Output 部分