Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
149 - The 2017 China Collegiate Programming Contest, Qinhuangdao Site - H
Prime Set

Time Limit: 1 Second      Memory Limit: 131072 KB

Given an array of $$n$$ integers $$a_1, a_2, \dots, a_n$$, we say a set $$\{i, j\}$$ is a prime set of the given array, if $$i \ne j$$ and $$a_i + a_j$$ is prime.

BaoBao has just found an array of $$n$$ integers $$a_1, a_2, \dots, a_n$$ in 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 $$|\bigcup\limits_{i = 1}^{m}p_i|$$ by carefully selecting $$m$$ and $$p_1, p_2, \dots, p_m$$, where $$m \le k$$ and $$p_i$$ is a prime set of the given array. Please help BaoBao calculate the maximum size of the union set.

#### Input

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 \le n \le 3\times 10^3$$, $$0 \le k \le \frac{n(n-1)}{2}$$), their meanings are described above.

The second line contains $$n$$ integers $$a_1, a_2, \dots, a_n$$ ($$1 \le a_i \le 10^6$$), indicating the given array.

It's guaranteed that the sum of $$n$$ over all test cases will not exceed $$10^4$$.

#### Output

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.

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

#### Hint

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.

Submit    Status