ITPTIT ICPC 2021

Time limit: 1s

Hôm nay, Liên Minh Huyền Thoại sinh nhật 10 năm tuổi, để kỉ niệm ngày này, Riot ra một bài toán và phần thưởng sẽ là trang phục siêu hiếm “NEO PAX Sivir” cho ai giải được. Bài toán như sau :

“Sức mạnh của 1 mảng là ước chung lớn nhất của mảng đó. Bạn được phép giảm đi mỗi số trong mảng 1 giá trị nào đó bất kì miễn sao giá trị đó không vượt quá k. Với mọi thao tác thay đổi mảng, ta được 1 mảng mới. Hãy tìm ra sức mạnh lớn nhất có thể tạo ra từ mảng ban đầu.”

Jackichul rất thích trang phục này vì tướng tủ của cậu là Sivir, vậy nên cậu quyết tâm giải bằng được bài toán trên. Các bạn hãy giúp cậu nhé!

Input

-Dòng đầu tiên chứa 2 số nguyên n, k ( 1 ≤ n ≤ 3.10⁵, 1 ≤ k ≤ 10⁶).

-Dòng thứ hai gồm n số nguyên (1 ≤ a_i ≤ 10⁶).

Output

In trên một dòng số nguyên duy nhất là kết quả bài toán.

Example

Input:
7 2
4 19 7 7 11 13 15

Output:
3