Cho số nguyên dương n, số nguyên k và dãy số nguyên a1, a2, …, an. Tìm độ dài dài nhất của dãy con gồm các phần tử liên tiếp có tổng các phần tử chia hết cho k. Hay tìm cặp (i,j) sao cho:

• a[i]+a[i+1]+… +a[j] chia hết cho k;

• j-i+1 lớn nhất

Input

• Dòng 1: chứa số n, k. (1 <= k <= 10^5)

• Dòng 2: chứa n số a1, a2, …, an (|ai|<=10^9)

Output

• Ghi ra độ dài dài nhất của dãy con tìm được.

Sample Input

9 4  
3 9 9 5 1 1 10 3 5

Sample Output

6

Giới hạn

Sub1: n≤5000    
Sub2: n≤1000000