For a given array B, we can divide the array into 2 non-empty [subsequences], such that, each element of the array is present in exactly one of the subsequences. 

Let X and Y denote the [GCD] of all elements of the first and second subsequence respectively.  
We define the *maximum diversity* of the array B as:

MXDV(B) = max(X - Y), over all possible pairs of subsequences.

Given an array A of N non-negative integers​ and a non-negative integer K, find the length of the smallest subarray S of array A such that MXDV(S) ≥ K.  
If no such subarray exists, print -1.

------ Input Format ------ 

- First line contains T − the number of test cases. The description of the test cases is as follows.
- The first line of each test case contains two integers N, K − the length of array A and the value of K.
- The second line of each test case contains N integers A_{1}, A_{2}, \ldots, A_{N}​. 

------ Output Format ------ 

For each test case, output a single integer − the length of the smallest subarray S of array A such that MXDV(S) ≥ K. If no such subarray exists, print -1.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ 10^{6}$
$1 ≤ A_{i} ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
3
6 5
10 3 9 12 12 8
6 8
10 3 9 12 12 8
6 10
10 3 9 12 12 8
----- Sample Output 1 ------ 
2
3
4
----- explanation 1 ------ 
Test case $1$: One possible subarray $S$ can be $[3, 9]$ and the subsequences thus formed can be $[9]$, $[3]$. The value of $X - Y = 9 - 3 = 6$. It can be shown that this is the smallest array for which $MXDV(S) = 6 ≥ 5$.

Test case $2$: One of the possible subarray $S$ can be $[10, 3, 9]$ and the subsequences thus formed can be $[9]$, $[10, 3]$. The value of $X - Y= 9 - 1 = 8$. It can be proven that there is no subarray $S$ with less than $3$ elements which can have $MXDV(S) = 8≥ 8$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Amortized analysis

Range queries

Complete search

Segment trees revisited

Number theory

Mathematics

Data structures


Solutions:
from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
from heapq import *
import functools
mod = 998244353
import sys
input = sys.stdin.readline
import typing

class SegTree:

	def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None:
		self._op = op
		self._e = e
		if isinstance(v, int):
			v = [e] * v
		self._n = len(v)
		self._log = self._n.bit_length()
		self._size = 1 << self._log
		self._d = [e] * (2 * self._size)
		for i in range(self._n):
			self._d[self._size + i] = v[i]
		for i in range(self._size - 1, 0, -1):
			self._update(i)

	def set(self, p: int, x: typing.Any) -> None:
		assert 0 <= p < self._n
		p += self._size
		self._d[p] = x
		for i in range(1, self._log + 1):
			self._update(p >> i)

	def get(self, p: int) -> typing.Any:
		assert 0 <= p < self._n
		return self._d[p + self._size]

	def prod(self, left: int, right: int) -> typing.Any:
		assert 0 <= left <= right <= self._n
		sml = self._e
		smr = self._e
		left += self._size
		right += self._size
		while left < right:
			if left & 1:
				sml = self._op(sml, self._d[left])
				left += 1
			if right & 1:
				right -= 1
				smr = self._op(self._d[right], smr)
			left >>= 1
			right >>= 1
		return self._op(sml, smr)

	def all_prod(self) -> typing.Any:
		return self._d[1]

	def max_right(self, left: int, f: typing.Callable[[typing.Any], bool]) -> int:
		assert 0 <= left <= self._n
		assert f(self._e)
		if left == self._n:
			return self._n
		left += self._size
		sm = self._e
		first = True
		while first or left & -left != left:
			first = False
			while left % 2 == 0:
				left >>= 1
			if not f(self._op(sm, self._d[left])):
				while left < self._size:
					left *= 2
					if f(self._op(sm, self._d[left])):
						sm = self._op(sm, self._d[left])
						left += 1
				return left - self._size
			sm = self._op(sm, self._d[left])
			left += 1
		return self._n

	def min_left(self, right: int, f: typing.Callable[[typing.Any], bool]) -> int:
		assert 0 <= right <= self._n
		assert f(self._e)
		if right == 0:
			return 0
		right += self._size
		sm = self._e
		first = True
		while first or right & -right != right:
			first = False
			right -= 1
			while right > 1 and right % 2:
				right >>= 1
			if not f(self._op(self._d[right], sm)):
				while right < self._size:
					right = 2 * right + 1
					if f(self._op(self._d[right], sm)):
						sm = self._op(self._d[right], sm)
						right -= 1
				return right + 1 - self._size
			sm = self._op(self._d[right], sm)
		return 0

	def _update(self, k: int) -> None:
		self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

class SparseTable:

	def __init__(self, v, op, e):
		self.N = len(v)
		self.op = op
		self.e = e
		self.lg = [self.e] * (self.N + 1)
		for i in range(2, self.N + 1):
			self.lg[i] = self.lg[i >> 1] + 1
		self.pow_2 = [pow(2, i) for i in range(20)]
		self.table = [None] * (self.lg[self.N] + 1)
		st0 = self.table[0] = [a for a in v]
		b = 1
		for i in range(self.lg[self.N]):
			st0 = self.table[i + 1] = [self.op(x, y) for (x, y) in zip(st0, st0[b:])]
			b <<= 1

	def prod(self, s, t):
		if s == t:
			return self.e
		b = t - s
		m = self.lg[b]
		return self.op(self.table[m][s], self.table[m][t - self.pow_2[m]])

def op(x, y):
	return math.gcd(x, y)
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedMultiset(Generic[T]):
	BUCKET_RATIO = 50
	REBUILD_RATIO = 170

	def _build(self, a=None) -> None:
		if a is None:
			a = list(self)
		size = self.size = len(a)
		bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
		self.a = [a[size * i // bucket_size:size * (i + 1) // bucket_size] for i in range(bucket_size)]

	def __init__(self, a: Iterable[T]=[]) -> None:
		a = list(a)
		if not all((a[i] <= a[i + 1] for i in range(len(a) - 1))):
			a = sorted(a)
		self._build(a)

	def __iter__(self) -> Iterator[T]:
		for i in self.a:
			for j in i:
				yield j

	def __reversed__(self) -> Iterator[T]:
		for i in reversed(self.a):
			for j in reversed(i):
				yield j

	def __len__(self) -> int:
		return self.size

	def __repr__(self) -> str:
		return 'SortedMultiset' + str(self.a)

	def __str__(self) -> str:
		s = str(list(self))
		return '{' + s[1:len(s) - 1] + '}'

	def _find_bucket(self, x: T) -> List[T]:
		for a in self.a:
			if x <= a[-1]:
				return a
		return a

	def __contains__(self, x: T) -> bool:
		if self.size == 0:
			return False
		a = self._find_bucket(x)
		i = bisect_left(a, x)
		return i != len(a) and a[i] == x

	def count(self, x: T) -> int:
		return self.index_right(x) - self.index(x)

	def add(self, x: T) -> None:
		if self.size == 0:
			self.a = [[x]]
			self.size = 1
			return
		a = self._find_bucket(x)
		insort(a, x)
		self.size += 1
		if len(a) > len(self.a) * self.REBUILD_RATIO:
			self._build()

	def discard(self, x: T) -> bool:
		if self.size == 0:
			return False
		a = self._find_bucket(x)
		i = bisect_left(a, x)
		if i == len(a) or a[i] != x:
			return False
		a.pop(i)
		self.size -= 1
		if len(a) == 0:
			self._build()
		return True

	def lt(self, x: T) -> Union[T, None]:
		for a in reversed(self.a):
			if a[0] < x:
				return a[bisect_left(a, x) - 1]

	def le(self, x: T) -> Union[T, None]:
		for a in reversed(self.a):
			if a[0] <= x:
				return a[bisect_right(a, x) - 1]

	def gt(self, x: T) -> Union[T, None]:
		for a in self.a:
			if a[-1] > x:
				return a[bisect_right(a, x)]

	def ge(self, x: T) -> Union[T, None]:
		for a in self.a:
			if a[-1] >= x:
				return a[bisect_left(a, x)]

	def __getitem__(self, x: int) -> T:
		if x < 0:
			x += self.size
		if x < 0:
			raise IndexError
		for a in self.a:
			if x < len(a):
				return a[x]
			x -= len(a)
		raise IndexError

	def index(self, x: T) -> int:
		ans = 0
		for a in self.a:
			if a[-1] >= x:
				return ans + bisect_left(a, x)
			ans += len(a)
		return ans

	def index_right(self, x: T) -> int:
		ans = 0
		for a in self.a:
			if a[-1] > x:
				return ans + bisect_right(a, x)
			ans += len(a)
		return ans
INF = 1 << 31
t = int(input())

def is_ok(x):
	ms = SortedMultiset([(a[i] << 30) + i for i in range(x - 1)])
	for i in range(n - x + 1):
		ms.add((a[i + x - 1] << 30) + (i + x - 1))
		(m1, mid1) = divmod(ms[-1], 1 << 30)
		if m1 - math.gcd(st.prod(i, mid1), st.prod(mid1 + 1, i + x)) >= k:
			return True
		(m2, mid2) = divmod(ms[-2], 1 << 30)
		if m2 - math.gcd(st.prod(i, mid2), st.prod(mid2 + 1, i + x)) >= k:
			return True
		ms.discard((a[i] << 30) + i)
	return False
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	st = SparseTable(a, op, 0)
	flg = 0
	for i in range(n):
		if a[i] - math.gcd(st.prod(0, i), st.prod(i + 1, n)) >= k:
			flg = 1
			break
	if not flg:
		print(-1)
		continue
	ok = n
	ng = 1
	while abs(ng - ok) > 1:
		mid = (ng + ok) // 2
		if is_ok(mid):
			ok = mid
		else:
			ng = mid
	print(ok)