Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Roy and Hridoy are good friends. They both love math. One day Roy preapared a problem to check his friend Hridoy's IQ level.
Problem is very simple, You are given an Array A[] of length \(N\). You need to find out the length of the longest subarray where the GCD of the subarray is greater than \(X\). Before you find longest subarray, you can do at most \(K\) operations (possibly zero) in the array,

in one operation :

• Select an index \(i\), \(1<=i<=N\) and increase \(i\)-th element by 1 (Ex. A[i]=A[i]+1)

Hridoy is busy with his University works and need your help to solve this problem.

Note: GCD means Greatest common divisor, GCD(2,4)=2, GCD(6,9,12)=3.

Input

First line takes two integer \(N,K\) : size of the array and maximum number of operations
second line takes \(N\) integers
\(1 <= N <= 10^5\)
\(1 <= K <= 10^7\)
\(1 <= X, Ai <= 100\)

Output

Print one integer : size of the maximum subarray

Sample

5 2 2
2 4 7 9 12

3

In the first testcase, Array A[]={2,4,7,9,12} and we can do at most K=2 operations.
First operation: select 3rd index and increase its value by 1. A[]={2,4,8,9,12};
Second operation: select 3rd index and increase its value by 1. A[]={2,4,9,9,12};

after that we can select the subarray from 3rd index to 5th index in which GCD(9,9,12)= 3 > X and the length of this subarray is 3 which is maximum.