In Jollybee Chess Championship 2008, there are a number of players who have withdrawn themselves from the championship of 64 players (in this problem, we generalized it into 2^N players). Due to the nature of the competition, which is a regular knock-out tournament, and also the short notice of the withdrawals, some matches had been walkover matches (also known as a w/o, a victory due to the absent of the opponent).

If both players are available then there will be a normal match, one of them will advance to the next phase. If only one player is available then there will be a walkover match, and he/she will automatically advance. If no player is available then there will be no match.

In the left figure, the player #3 and #4 are withdrawn from the tournament, leaving a total of one w/o match (at match #3).

Given the list of players who withdraw right before the tournament start, calculate how many w/o matches to happen in the whole tournament, assuming that all of the remaining players play until the end of the tournament (winning or knocked-out).

Input 

The first line of input contains an integer T , the number of test cases to follow. Each case begins with two integers, N (1N10) and M (0M2^N) . The next line contains M integers, denoting the players who have withdrawn themselves right before the tournament. The players are numbered from 1 to 2^N , ordered by their position in the tournament draw.

Output 

For each case, print in a single line containing the number of walkover matches.

Sample Input 

3 
2 2 
3 4 
3 5 
1 2 3 4 5 
2 1
2

Sample Output 

1 
2 
1

#include <stdio.h>
#include <string.h>

int main() {
    int testcase;
    int n, m, i, x;
    int tree[8192];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        int M = 1<<n;
        memset(tree, 0, sizeof(tree));
        for(i = 0; i < m; i++) {
            scanf("%d", &x), x--;
            tree[M+x] = -1;
        }
        int wo = 0;
        for(i = M-1; i >= 1; i--) {
            int l = tree[i<<1], r = tree[i<<1|1];
            if(l == -1 && r == -1)
                tree[i] = -1;
            else if(l == 0 && r == 0) {}
            else {
                wo++;
            }
        }
        printf("%d\n", wo);
    }
    return 0;
}