# 描述

Given an array of $n$ integers $a_1, a_2, \dots, a_n$, we say a set $\lbrace i, j\rbrace$ 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.

## 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.

# 思路

• 考虑所有的质数除了$2$之外都是奇数，所以除去$1,1$的匹配之外，都是一奇一偶的匹配。显然是个二分图匹配。所以可以先建图跑一遍二分图匹配，得到最大匹配。每个匹配对答案的贡献为$2$。
• 然后再看有没有$1,1$的匹配，这也是对答案贡献为$2$。然后考虑对答案贡献为$1$的部分，即一个已经被匹配了，而另一个没有被匹配的情况。

0%