Problem Statement

You are given a sequence of length $N$ consisting of non-negative integers: $A=(A _ 1,A _ 2,\ldots,A _ N)$.

Define the score of a sequence of length $1$ or more consisting of sequences of non-negative integers, $S=(S _ 1,S _ 2,\ldots,S _ k)$, as the number of sequences $S _ i\ (1\le i\le k)$ whose sum of elements is divisible by $K$.

Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing $A$ into one or more contiguous subsequences. Here, dividing a sequence $A$ of length $N$ into one or more contiguous subsequences means choosing a sequence of integers $l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N)$ of length $1$ or more, and forming the following $k$ sequences.

• $(A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k)$ (Here, let $l _ {k+1}=N+1$.)

Constraints

• $1\le N\le2\times10 ^ 5$
• $1\le K\le10 ^ 9$
• $0\le A _ i\lt K$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $K$
• $A _ 1$ $A _ 2$ $\ldots$ $A _ N$

Output

Output the answer.

6 10
6 8 2 2 6 4

2

For example, $A$ can be divided into four contiguous subsequences as $(6),(8,2),(2),(6,4)$. The sums of the elements of the second and fourth sequences are multiples of $10$, so the score of $((6),(8,2),(2),(6,4))$ is $2$.

$A$ cannot be divided so that the score is $3$ or more, so output 2.

8 1
0 0 0 0 0 0 0 0

8

30 8
5 0 4 2 7 3 2 3 2 4 0 1 4 0 4 1 7 5 2 5 0 3 6 6 2 3 2 2 4 2

8

• Source: AtCoder ABC 473 E