Time Limit: 3.0 s

Memory Limit: 512.0 MB

Description

You are given an array \(A[]\) of length \(N\).

An array of length N is called \(X\)-ordinary if

• the length of the array is 1 and \(gcd(A_i,X)>1\)
• or , one half of the array is \((X+1)\)-ordinary and in another half for each index \(i\), \(gcd(A_i,X)>1\)

You can perform the following operation any number of time :

• Select an index \(i (1 ≤ i ≤ N)\), and increase \(A_i\) by one.

What is the minimum number of operations needed to make the array \(X\)-ordinary.

Note : An array can only be divided into two half in the following way.
first half \([1 - n/2]\)
last half \([(n/2)+1 - n]\)
where \(n\) is the current size of the array

Input

• The first line contains two integers \(N\) (the size of the array) and \(X\) (the integer used for the conditions) (\(1 ≤ N ≤ 2 * 10^5\)) and (\(1 ≤ X ≤ 10^9\)).
• The second line contains \(N\) integers, the elements of the array \(A[]\), where (\(1 ≤ A[i] ≤ 10^9\)).

Output

• Print one integer : minimum number of operation needed to make the array \(X\)-ordinary , if it is impossible to make the array \(X\)-ordinary then print -1

Sample

3 2
2 7 3

1

in the given testcase : the array can be changed as \([2,8,3]\) by applying only one operation and this is a \(2-ordinary\) array because:

• all the element of the left part \([2]\) of the array has a gcd > 1 with 2 and the other part [8,3] is a \(3-ordinary\) array.

the other part \([8,3]\) is a \(3-ordinary\) array because :

• all the elements of the right part \([3]\) of the array has a gcd > 1 with 3 and the other part \([8]\) is a \(4-ordinary\) array

the other part \([8]\) is a \(4-ordinary\) array because

• it has only one element and the element has a gcd > 1 with 4