Just as the title indicates, this problem is pretty simple. Given you a truth Table of a logic function and you can express it with a sum of product form which product’s priority is higher than sum (Like  ) here ‘∧’ means logic gate “and”, ‘∨’ means the logic gate “or”, and ‘¬’ means the logic gate “not”, and the cost of this function is

2 * 2 + 3 = 7 (two “and” gate with 2 inputs, one “and” gate with 3 inputs, here we just consider “and” gates’ costs)

But we can simplify it to a better form like as we all know, and cost is just 4, so the question is how you gain a minimum cost of a logic function which described by a truth table. Truth table is defined as follow:

x1  x2  x1∧x2

0   0    0

0   1    0

1   0    0

1   1    1

The cost is the sum of inputs of all “and” gates.

 First an integer T witch means the number of test cases, and then followed by T cases.

      The first line of each case is an integer n which means the number of logic variable, then an integer m indicates how much ‘1’(true) outputs in the truth table of the logic function followed by a line has m integer a[i] denote the decimal form inputs for the logic function returns 1(true).

       (1<= T <= 10)

       (1<= n <= 8)

       (1<= m <=50)

       (0<= a[i] <2ⁿ)

An integer denote the minimum cost of the logic function (note if logic function always return 0 or 1,then just output 0 means no “and” gate needed)

2
2 1
3
4 9
7 8 9 10 11 12 13 14 15

2
4

         The first case exactly defined function “and” (x1∧x2),

       F(1,1) = 1

       The second case is the example show in the problem (x1∨(x2∧x3∧x4))

       F(0,1,1,1) = 1              

       F(1,0,0,0) = 1                     

       F(1,0,0,1) = 1

       F(1,0,1,0) = 1

       F(1,0,1,1) = 1

       F(1,1,0,0) = 1

       F(1,1,0,1) = 1

          F(1,1,1,1) = 1