A school has to decide on its team for an international quiz. There are $n$ students in the school. We can describe the students using an array $a$ where $a_i$ is the smartness of the $i$-th ($1 \le i \le n$) student.

There are $m$ topics $1, 2, 3, \ldots, m$ from which the quiz questions will be formed. The $i$-th student is considered proficient in a topic $T$ if $(a_i mod T) = 0$. Otherwise, he is a rookie in that topic.

We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic.

Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ and $m$ ($1 \le n,m \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print the answer on a new line. If there is no solution, output $-1$.


-----Examples-----

Input
3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7
Output
-1
0
3


-----Note-----

In the first test case, we have participants with smartnesses $3$ and $7$, and $m = 4$. Thus, there is no student with smartness divisible by $2$. Since $2 \leq m$, there is no way to choose a team.

In the second test case, we can select the participant with smartness $2$ to be the only one on the team. This way the team will be collectively proficient in both topics $1$ and $2$.

In the third test case, consider the team with participants of smartnesses $4, 5, 6, 7$. This way the team will be collectively proficient in all topics $1, 2, \ldots, 7$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting

Amortized analysis

Mathematics


Solutions:
N = int(input())
from collections import defaultdict
M = defaultdict(lambda : [])
for i in range(1, int(100000.0) + 1):
	for j in range(i, int(100000.0) + 1, i):
		M[j].append(i)

def solve():
	(n, m) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A.sort()
	freq = {}
	(l, i) = (0, 0)
	res = 100000
	while i < n:
		for fac in M[A[i]]:
			if fac > m:
				break
			if fac not in freq:
				freq[fac] = 0
			freq[fac] += 1
		while len(freq) == m:
			res = min(res, A[i] - A[l], res)
			for fac in M[A[l]]:
				if fac > m:
					break
				freq[fac] -= 1
				if freq[fac] == 0:
					del freq[fac]
			l += 1
		i += 1
	print(res if res != 100000 else -1)
for i in range(N):
	solve()


import math
from collections import defaultdict
from itertools import accumulate

def check(num):
	for fac in memo[num]:
		if m >= fac >= mod and rmd[fac - mod] == 1:
			return False
	return True

def update(num):
	for fac in memo[num]:
		if m >= fac >= mod:
			rmd[fac - mod] -= 1
N = 100000
memo = defaultdict(list)
for i in range(1, N + 1):
	for j in range(i, N + 1, i):
		memo[j].append(i)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(set(map(int, input().split())))
	n = len(a)
	a.sort()
	mod = m // 2 + 1
	rmd = [0] * (m - m // 2)
	z = m - m // 2
	l = n
	for i in range(n):
		if a[i] // mod > 0:
			l = i
			break
	ans = math.inf
	for i in range(l, n):
		for fac in memo[a[i]]:
			if m >= fac >= mod:
				if rmd[fac - mod] == 0:
					z -= 1
					assert z > -1
				rmd[fac - mod] += 1
		while l < i and check(a[l]):
			update(a[l])
			l += 1
		if z == 0:
			ans = min(ans, a[i] - a[l])
	if ans == math.inf:
		print(-1)
	else:
		print(ans)