Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Again GCD Challenge

By Taran106 · Limits 1s, 512 MB

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

InputOutput
4 2
6 10 22 18
3
InputOutput
2 1
2 4
0

    Discussion

    Statistics


    76% Solution Ratio

    YouKnowWhoEarliest, 3w ago

    akash740Fastest, 0.0s

    sajib_biswasLightest, 1.3 MB

    tanvirtareqShortest, 839B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.