1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
using namespace std;
typedef long long ll;
inline int in()
{
    int res=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-48,c=getchar();
    return res;
}
inline ll max(ll a, ll b)
{
    return a > b ? a : b;
}
void out(ll x)
{
    if (x>9) out(x/10);
    putchar(x%10+48);
}
const int mod = 1e9 + 7, maxn = 1e5 + 5;
int dp[1 << 20][2];
int main()
{
    int t = in();
    while (t--){
        int x, n, p = 0, ma = 0;
        n = in();
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX