Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~. Trong mỗi thao tác, ta có thể thay thế hai phần tử bất kỳ bởi tổng của chúng (tổng đó có thể chèn vào vị trí bất kỳ trong dãy).

Yêu cầu: Hãy lập trình để tìm số tối đa các phần tử chia hết cho số nguyên ~K~ trong dãy kết quả sau khi thực hiện một số lần tùy ý các thao tác nói trên.

Dữ liệu vào

Đọc từ tệp văn bản MODK.INP gồm:

• Dòng đầu ghi hai số nguyên dương ~n~ và ~K~;
• Dòng thứ hai ghi dãy số ~a_1, a_2, \ldots, a_n~;
• Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết quả

Ghi vào tệp văn bản MODK.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Input:

5 4
2 3 4 5 6

Output:

3

Giải thích: ~2\ 3\ 4\ 5\ 6 \rightarrow 4\ 8\ 8~ (sau 2 thao tác biến đổi để có dãy gồm tối đa 3 phần tử chia hết cho 4).

Giới hạn

• ~n, K \le 10^5~
• ~0 < a_i \le 10^9~ (~1 \le i \le n~)
• Có ~30\%~ số điểm tương ứng với ~n \le 10^3~, ~K = 4~ và ~a_i \le 10^6~.
• Có ~30\%~ số điểm tương ứng với ~n \le 10^3~, ~K = 5~ và ~a_i \le 10^6~.
• Có ~40\%~ số điểm tương ứng với trường hợp còn lại.