You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你 对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。

Format

Input

第一行为两个整数 n, K, 以空格分隔，第二行为 n 个整数，表示 $a[1] ∼ a[n]，1 ≤ n ≤ 10^5 , 1 ≤ a[i] ≤ 10^9 , 1 ≤ nK ≤ 10^7$

Output

输出一个整数表示最长子序列的长度 m

Samples

7 5
10 3 4 2 2 9 8

6