Cậu bé Nobita đang học code để chuẩn bị trở thành một lập trình viên. Nobita gặp phải một bài toán khó. Cho dãy số nguyên \(N\) và số nguyên \(K\), hãy tìm ra kích thước đoạn con dài nhất gồm các phần tử liên tiếp sao cho tổng các phần tử này chia hết cho \(K\). Các bạn hãy giúp Nobita nhé.

Input

Dòng đầu gồm 2 số nguyên dương \(N,K\) (1 <= \(N\),\(K\) <= \(10^5\))

\(N\) dòng tiếp theo, mỗi dòng gồm một số nguyên (\(a[1]\), \(a[2]\), ...\(a[n]\)) đại diện cho giá trị các phần tử của dãy số (0 <= a[i] <= \(10^5\))

Output

Một dòng duy nhất là đáp án của đề bài

Ví dụ

Input

5 4
6
0
3
5
1

Output

3

Giải thích Đoạn con thoả mãn là [0, 3, 5] có tổng là 8 => Đáp là 3