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