Again GCD Challenge

You will be given a number X. Now consider any sequence extra ordinary if its length is at least 2 and GCD of every possible pair of elements you pick from this sequence is X.

You are also given an array A of length N. Find the length of the longest extra ordinary subarray in the given array.

Input

The first line of input contains an integer N which is the number of elements in array A and the integer X.

The next line contains N integers Ai, elements of the array A.

Constraints

• 1 ≤ N ≤ 10^5

• 1 ≤ X ≤ 10^5

• 1 ≤ Ai ≤ 2*10^5

Output

Print the length of the longest extra ordinary subarray in the given array A.

Samples

Input	Output
4 2 6 10 22 18	3

Input	Output
2 1 2 4	0