Prime Set
题号：NC14372
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Given an array of n integers a1,a2,...,an,we say a set {i,j}  is a prime set of the given array, if i ≠ j and ai + aj is prime.

BaoBao has just found an array of n integers a1,a2,...,anin his pocket. He would like to select at most k prime set of that array to maximize the size of the union of the selected sets. That is to say, to maximize   by carefully selecting m and p1,p2,...pm, where m ≤ k and pi is a prime set of the given array. Please help BaoBao calculate the maximum size of the union set.

输入描述:

There are multiple test cases. The first line of the input is an integer T ,indicating the number of test cases. For each test case:

The first line contains two integers n and k (1 ≤ n ≤ 3 × 103,0 ≤ k ≤ ), their meanings are described above.

The second line contains n integers a1,a2,...,an, (1 ≤ ai ≤ 106) , indicating the given array.

t's guaranteed that the sum of n over all test cases will not exceed 104.

输出描述:

For each test case output one line containing one integer, indicating the maximum size of the union of at most  k prime set of the given array.
示例1

输入

复制 
4
4 2
2 3 4 5
5 3
3 4 12 3 6
6 3
1 3 6 8 1 1
1 0
1

输出

复制 
4
3
6
0

说明

For the first sample test case, there are 3 prime sets: {1, 2}, {1, 4} and {2, 3}. As k = 2,we can select {1, 4} and {2, 3} to get the largest union set {1, 2, 3, 4} with a size of 4.
For the second sample test case, there are only 2 prime sets: {1, 2} and {2, 4}. As k = 3, we can select both of them to get the largest union set {1, 2, 4} with a size of 3.
For the third sample test case, there are 7 prime sets: {1, 3}, {1, 5}, {1, 6}, {2, 4}, {3, 5}, {3, 6} and {5, 6}. As  k = 3,we can select {1, 3}, {2, 4} and {5, 6} to get the largest union set {1, 2, 3, 4, 5, 6} with a size of 6.