Chemical Compounds

Little Werner, after settling his differences with Bor, decided to engage seriously in research and discover a new synthetic substance. Determined, he rushes to the nearest factory to procure chemical elements.

On that day, the factory has N available chemical elements placed in a sequence. The atomic number of the elements is known, and Werner is willing to buy as many as he can and use them all for his new synthetic substance. However, he knows he must be careful with his choices, as he has observed that when he combines two elements whose sum of atomic numbers is a multiple of the number K, an explosion occurs, and he wants to avoid that. Also, he knows that the elements he decides to buy should be consecutive in the sequence, as it is easier and more economical to extract them together as a group rather than individually.

Little Werner is in a hurry to return to his laboratory, and as he struggles to find out the maximum number of elements he can buy, he assigns this problem to you.

Problem

Develop a program in one of the languages PASCAL, C, C++, Java that reads the values of N and K, as well as the atomic numbers of the elements in order, and prints the maximum number of elements Werner can buy.

Input

The input file named chemicals.in is a text file with the following structure. The first line contains two integers, N (the number of chemical elements) and K, separated by a space. The next line contains the N atomic numbers A_i (where ~1 \le i \le N~) of the chemical elements, in order.

Output

The output file named chemicals.out is a text file containing a single line with an integer: the maximum number of elements Werner can buy.

Examples of Input - Output Files:

1ο

STDIN (chemicals.in)

3 5
1 2 1

STDOUT (chemicals.out)

3

Explanation: Werner can take all three elements in the series.

2ο

STDIN (chemicals.in)

6 3
6 7 9 1 4 5

STDOUT (chemicals.out)

4

Explanation: Werner can take the four elements ~7~, ~9~, ~1~, and ~4~, which are compatible with each other. It is not beneficial for him to take ~6~ because ~6+9=15~, which is a multiple of ~3~ and then he should not take ~9~. Also, it is not beneficial for him to take ~5~ because ~4+5=9~, which is also a multiple of ~3~.

3ο

STDIN (chemicals.in)

8 13
13 12 14 10 8 12 10 8

STDOUT (chemicals.out)

5

Constraints:

• ~1 \le N \le 1.000.000~
• ~1 \le K \le 1.000.000.000~
• ~1 \le A_i \le 1.000.000.000~
• The atomic numbers of the elements are not necessarily distinct.
• For test cases with a total value of 30%, ~K = 3~.
• For test cases with a total value of 50%, ~N \le 10.000~.

Attention! Ensure efficient input reading and output printing, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.