#include <bits/stdc++.h>
using namespace std;
//x = no of '[' - no of ']'
//1)pehle se kaheen kaheen pe "[" daale hue hai jo hamein expressions mile hai usmei
int squarebrackets(char * arr,int n,int x){ // 'x' gives the diffrence between open brackts and closed ones-->
if(n == 0 && x == 0){ //n == 0 means array khatam ho chuka hai-->x == 0 hona chaiyye kyuki no of open brackets and closed one should be equal
return 1;
}
if(n == 0 && x != 0){//matlab array khatam but we have more '[' than ']' matlab galat expression--> wont count it
return 0;
}
if(arr[0] == 'z'){ //yahaan kuch nhi hai -->we can put up an open or close
if(x == 0 ){// special case 1)x == 0 matlab sab baanced hai --> open bracket hi dal sakta hai hence--> x increases by one
return squarebrackets(arr + 1,n - 1, 1);
}
if(x == n){// special case 2) x == n -> '[' are graeter by just that amount jitna array bacha hai-->ab bache mai sirf '] ' lagega no option
return 1;
}else{
return squarebrackets(arr + 1,n - 1,x + 1) + squarebrackets(arr + 1,n - 1,x - 1); //general case mei ek baar arr[0] ='[' daal ke ans mangwa lo
//and ek baar ']' baar arr[0]= ']'karke ans mangwa lo then erturn their sum
}
}
else if(arr[0] != 'z'){ //it means arr[0] pe '[' already dala hua hai-->so,no option
//(arr[0] == '['){
return squarebrackets(arr + 1,n - 1,x + 1);
}
}
int main()
{
int A;
cin >> A;
for(int c = 0;c < A;c++){
int n;
cin >> n;
n = 2*n;
char* arr = new char[ n];
int k;
for(int i = 0;i < n;i++){ //i'll fill the array with 'z'
arr[i] = 'z';
}
cin>>k;
for(int i = 0;i < k;i++){
int t;
cin >> t;
arr[t-1] = '['; //jahaan '['daalna hai vaha replace 'z' with '['
}
int ans = squarebrackets(arr,n,0);//x = 0 bheja hai kyuki abhi that difference is 0
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovL3ggPSBubyBvZiAnWycgLSBubyBvZiAnXScKLy8xKXBlaGxlIHNlIGthaGVlbiBrYWhlZW4gcGUgIlsiIGRhYWxlIGh1ZSBoYWkgam8gaGFtZWluIGV4cHJlc3Npb25zIG1pbGUgaGFpIHVzbWVpIAoKaW50IHNxdWFyZWJyYWNrZXRzKGNoYXIgKiBhcnIsaW50IG4saW50IHgpeyAvLyAneCcgZ2l2ZXMgdGhlIGRpZmZyZW5jZSBiZXR3ZWVuIG9wZW4gYnJhY2t0cyBhbmQgY2xvc2VkIG9uZXMtLT4KICAgIGlmKG4gPT0gMCAmJiB4ID09IDApeyAvL24gPT0gMCBtZWFucyBhcnJheSBraGF0YW0gaG8gY2h1a2EgaGFpLS0+eCA9PSAwIGhvbmEgY2hhaXl5ZSBreXVraSBubyBvZiBvcGVuIGJyYWNrZXRzIGFuZCBjbG9zZWQgb25lIHNob3VsZCBiZSBlcXVhbAogICAgICByZXR1cm4gMTsKICAgIH0KICAgIGlmKG4gID09IDAgJiYgeCAhPSAwKXsvL21hdGxhYiBhcnJheSBraGF0YW0gYnV0IHdlIGhhdmUgbW9yZSAnWycgdGhhbiAnXScgbWF0bGFiIGdhbGF0IGV4cHJlc3Npb24tLT4gd29udCBjb3VudCBpdCAKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBpZihhcnJbMF0gPT0gJ3onKXsgLy95YWhhYW4ga3VjaCBuaGkgaGFpIC0tPndlIGNhbiBwdXQgdXAgYW4gb3BlbiBvciBjbG9zZQogICAgICAgIGlmKHggPT0gMCApey8vIHNwZWNpYWwgY2FzZSAxKXggPT0gMCBtYXRsYWIgc2FiIGJhYW5jZWQgaGFpIC0tPiBvcGVuIGJyYWNrZXQgaGkgZGFsIHNha3RhIGhhaSBoZW5jZS0tPiB4IGluY3JlYXNlcyAgYnkgb25lCiAgICAgICAgICByZXR1cm4gc3F1YXJlYnJhY2tldHMoYXJyICsgMSxuIC0gMSwgMSk7CiAgICAgICAgfQogICAgICAgIGlmKHggPT0gbil7Ly8gc3BlY2lhbCBjYXNlIDIpIHggPT0gbiAtPiAnWycgYXJlIGdyYWV0ZXIgYnkganVzdCB0aGF0IGFtb3VudCBqaXRuYSBhcnJheSBiYWNoYSBoYWktLT5hYiBiYWNoZSBtYWkgc2lyZiAnXSAnIGxhZ2VnYSBubyBvcHRpb24KICAgICAgICAgIHJldHVybiAxOwogICAgICAgIH1lbHNlewogICAgICAgICAgICByZXR1cm4gc3F1YXJlYnJhY2tldHMoYXJyICsgMSxuIC0gMSx4ICsgMSkgKyBzcXVhcmVicmFja2V0cyhhcnIgKyAxLG4gLSAxLHggLSAxKTsgLy9nZW5lcmFsIGNhc2UgbWVpIGVrIGJhYXIgYXJyWzBdID0nWycgZGFhbCBrZSAgYW5zIG1hbmd3YSBsbwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9hbmQgZWsgYmFhciAnXScgYmFhciBhcnJbMF09ICddJ2thcmtlIGFucyBtYW5nd2EgbG8gdGhlbiBlcnR1cm4gdGhlaXIgc3VtCiAgICAgICAgfQogICAgfQogICAgCiAgICBlbHNlIGlmKGFyclswXSAhPSAneicpeyAgIC8vaXQgbWVhbnMgYXJyWzBdIHBlICdbJyBhbHJlYWR5IGRhbGEgaHVhIGhhaS0tPnNvLG5vIG9wdGlvbgogICAgICAgIC8vKGFyclswXSA9PSAnWycpewogICAgICAgICAgICByZXR1cm4gc3F1YXJlYnJhY2tldHMoYXJyICsgMSxuIC0gMSx4ICsgMSk7CiAgICAgICAgCiAgICAgICAKICAgIH0KfQoKaW50IG1haW4oKQp7CiAgICBpbnQgQTsKICAgIGNpbiA+PiBBOwogICAgZm9yKGludCBjID0gMDtjIDwgQTtjKyspewogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgICAgICBuID0gMipuOwogICAgY2hhciogYXJyID0gbmV3IGNoYXJbIG5dOwogICAgaW50IGs7CiAgICBmb3IoaW50IGkgPSAwO2kgPCAgbjtpKyspeyAgIC8vaSdsbCBmaWxsIHRoZSBhcnJheSB3aXRoICd6JwogICAgICAgIGFycltpXSA9ICd6JzsKICAgIH0KICAgIGNpbj4+azsgCiAgICBmb3IoaW50IGkgPSAwO2kgPCBrO2krKyl7CiAgICAgICAgaW50IHQ7CiAgICAgICAgY2luID4+IHQ7CiAgICAgICAgYXJyW3QtMV0gPSAnWyc7ICAgICAgICAgLy9qYWhhYW4gJ1snZGFhbG5hIGhhaSB2YWhhIHJlcGxhY2UgJ3onIHdpdGggJ1snCiAgICB9CiAgICAKICAgIGludCBhbnMgPSBzcXVhcmVicmFja2V0cyhhcnIsbiwwKTsvL3ggPSAwIGJoZWphIGhhaSBreXVraSBhYmhpIHRoYXQgZGlmZmVyZW5jZSBpcyAwCiAgICBjb3V0IDw8ICBhbnMgPDwgZW5kbDsKICAgIAp9CiAgICByZXR1cm4gMDsKfQ==