소수 카드 게임

Albert는 친구들과 소수 (prime) 카드 게임을 하기로 했다. 총 m명의 플레이어가 있고, 양의 정수가 하나씩 적혀있는 n장의 카드가 있다. 편의상 카드에 적힌 수를 v[1], v[2], ..., v[n]이라 하자.

먼저 플레이어들에게 카드를 나눠준 후, 각자 점수를 계산하여 승자를 가린다.

n장의 카드는 아래 규칙에 따라 m명의 플레이어에게 나누어져야 한다:

1. 각 카드는 반드시 한 명의 플레이어에게 주어진다.
2. 각 플레이어는 최소 한 장의 카드를 받는다.

n장의 카드를 모두 분배한 후 아래 규칙에 따라 각자 점수를 계산한다:

1. 먼저, 자신이 받은 카드에 적힌 수를 모두 더한다. 이를 S라 하자.
2. S에 가장 가까우면서 S가 아닌 소수(prime number)를 P라 하자 (그런 소수가 여럿인 경우 아무 것 하나를 P라 한다).
3. 해당 플레이어의 점수는 | S - P | 이다 ('|'는 절대값 기호이다).

예를 들어 n = m = 3이고 카드에 적힌 수가 [1, 2, 3]이라 하자. 이 때, 각 플레이어는 정확히 한 장씩 카드를 받는다.

• 1이 적힌 카드를 받은 플레이어의 점수는 1이다 (1에 가장 가까운 소수는 2이다).
• 2가 적힌 카드를 받은 플레이어의 점수는 1이다 (2에 가장 가까운 (2가 아닌) 소수는 3이다).
• 3이 적힌 카드를 받은 플레이어의 점수느 1이다 (3에 가장 가까운 소수는 2이다).
• 이 예제에서는 모든 플레이어의 점수가 1로 동일하다 (모두가 공동 승자이다).

다른 예로, n = 3, m = 2이고 카드에 적힌 수가 [23, 29, 41]이라 하자. 이 때, 한 플레이어는 카드 한 장을 받고 다른 플레이어는 두 장을 받게 된다. 아래와 같은 세 가지 방법으로 카드를 분배할 수 있다.

• 방법 1: [23] 과 [29, 41]로 분배하는 경우, 23에 가장 가까운 소수는 19이고 (29+41)에 가장 가까운 소수는 71이다. 따라서 두 플레이어의 점수는 각각 4와 1이다.
• 방법 2: [29] 과 [23, 41]로 분배하는 경우, 29에 가장 가까운 소수는 31이고 (23+41)에 가장 가까운 소수는 67이다. 따라서 두 플레이어의 점수는 2로 같다.
• 방법 3: [41] 과 [23, 29]로 분배하는 경우, 41에 가장 가까운 소수는 43이고 (23+29)에 가장 가까운 소수는 53이다. 따라서 두 플레이어의 점수는 각각 2와 1이다.

Albert는 게임의 흥미를 위해 승자의 점수가 최소가 되도록 카드를 나눠주고 싶다. 위에 언급한 두 번째 예제의 경우 방법 1은 승자의 점수가 4이고 방법 2와 3은 승자의 점수가 2가 되므로 정답은 2가 된다. Albert가 달성 할 수 있는 승자의 점수 최소값을 구해보자. 

소수 (prime number): 양의 정수 P가 1보다 크고 P의 약수가 1과 P뿐이면 소수이다.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 줄에 걸쳐 주어진다.

첫 줄에 n과 m이 공백으로 구분되어 주어진다.

둘째 줄에 n개의 정수가 (v[1], ..., v[n]) 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• 1 ≤ T ≤ 6
• 1 ≤ m ≤ n ≤ 15
• 1 ≤ v[i] ≤ 5,000,000
• v[i]의 총합 <= 5,000,000