#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX_NUM 5int min;unsigned long long set[2 * MAX_NUM * (MAX_NUM + 1)];int set_num;unsigned long long opt[2 * MAX_NUM * (MAX_NUM + 1)];unsigned long long state;int count[2 * MAX_NUM * (MAX_NUM + 1)];int shift[MAX_NUM] = {0, 25, 41, 50, 54};int minMax[] = {0, 1, 3, 6, 9, 12};const int lut[256] ={ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};int count1(unsigned long long x) { int i, ret = 0; for (i = 0; i < 64; i += 8) ret +=lut[(x >> i) & 0xff]; return ret;}int ullCmp(const void* a, const void* b){ unsigned long long* ull_a = (unsigned long long*)a; unsigned long long* ull_b = (unsigned long long*)b; return count1(state&*ull_b) - count1(state&*ull_a);}void preSet(int n){ state = 0; int l, i, j, s, t; for (l = 1; l <= n; l++) { for (i = 0; i <= n - l; i++) { for (j = 0; j <= n - l; j++) { state |= (unsigned long long)1 << (i * (n - l + 1) + j + shift[l - 1]); for (s = 0; s <= l + 1; s++) { if (s == 0) { for (t = 0; t <= l - 1; t++) set[(2 * n + 1) * i + j + t] &= ~((unsigned long long)1 << (i * (n - l + 1) + j + shift[l - 1])); } else if (s == l + 1) { for (t = 0; t <= l - 1; t++) set[(2 * n + 1) * (i + l) + j + t] &= ~((unsigned long long)1 << (i * (n - l + 1) + j + shift[l - 1])); } else { set[(2 * n + 1) * (i + s - 1) + j + n] &= ~((unsigned long long)1 << (i * (n - l + 1) + j + shift[l - 1])); set[(2 * n + 1) * (i + s - 1) + j + n + l] &= ~((unsigned long long)1 << (i * (n - l + 1) + j + shift[l - 1])); } } } } }}void init(int n){ int i, j; for (i = 0; i < 2 * n * (n + 1); i++) { for (j = 0; j < 2 * n * (n + 1) && opt[i] == 0; j++) { if (i != j && opt[j] == 0) { if (set[i] == set[j] || ((set[i] & ~set[j]) == 0 && (set[j] & ~set[i]) != 0)) opt[j] = 1; else if ((set[j] & ~set[i]) == 0 && (set[i] & ~set[j]) != 0) opt[i] = 1; } } } set_num = 0; for (i = 0; i < 2 * n *(n + 1); i++) { if (opt[i] == 0) set[set_num++] = set[i]; } qsort(set, set_num, sizeof (unsigned long long), ullCmp); opt[set_num - 1] = set[set_num - 1]; for (i = set_num - 2; i >= 0; i--) opt[i] = set[i] & opt[i + 1]; for (i = 0; i < set_num; i++) count[i] = count1(~set[i]); count[set_num] = 1; }void dfs(int s, int cur, int n, unsigned long long state){ if (state == 0) { if (min > cur) min = cur; return; } if (cur >= min - 1) return; int state_count = count1(state); int i; for (i = s; i < set_num && (state & opt[i]) == 0 && cur + 1 + state_count / count[i + 1] < min; i++) { if ((state & set[i]) < state) dfs(i + 1, cur + 1, n, state & set[i]); }}int main(){ int case_num; int n, k; int m; int i; scanf("%d", &case_num); while (case_num-- > 0) { memset(opt, 0, sizeof (opt)); memset(set, -1, sizeof (set)); scanf("%d", &n); preSet(n); scanf("%d", &k); for (i = 0; i < k; i++) { scanf("%d", &m); opt[m - 1] = 1; state &= set[m - 1]; } init(n); min = minMax[n]; dfs(0, 0, n, state); printf("%dn", min); } return 0;}
