Problem Description

Matt has N friends. They are playing a game together.

Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.

 

Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10⁶).

In the second line, there are N integers ki (0 ≤ k_i ≤ 10⁶), indicating the i-th friend’s magic number.

 

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

 

Sample Input

 

Sample Output

 

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<set>

#include<vector>

using namespace std;

#define INF 0x3f3f3f3f

#define eps 1e-10

#define ll long long

int const maxn = (<<);

const int mod = 1e9 + ;

int gcd(int a, int b) {

    if (b == ) return a;  return gcd(b, a % b);

}

int a[];

ll dp[][maxn];

int main()

{

    int t;

    scanf("%d",&t);

    int ca=;

    while(t--)

    {

        int n,m;

        memset(dp,,sizeof(dp));

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        dp[][]=;

        for(int i=;i<=n;i++)

            for(int j=;j<maxn;j++)

                dp[i][j]=dp[i-][j]+dp[i-][j^a[i]];   //如果前i-1个数异或值是j就不需要将第i个数进行异或，如果前i-1个数有异或后是j^a[i]的，那么第i个数进行异或，刚好可以得j

        ll ans=;

        printf("Case #%d: ",ca++);

        for(int i=m;i<maxn;i++)

            ans+=dp[n][i];

        printf("%lld\n",ans);

    }

    return ;

}