// problem - I
#include<bits/stdc++.h>
using namespace std;

const int M = 998244353;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin>>n>>k;

    long long ans = 0, must = 0;
    for (int i=1; i<=n; i++) {
        long long x;
        cin>>x;

        long long rem = 1LL<<(k-__builtin_popcountll(must));
        must |= x;
        long long cur = 1LL<<(k-__builtin_popcountll(must));
        ans += i*((rem-cur)%M);
    }


    cout<<ans%M<<endl;
}


// problem - B
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG printf("Hi\n")
#define i64 long long int
#define ui64 unsigned long long int
#define xx first
#define yy second
#define ln 17
#define off 302

#define IN freopen("circular_circles_input.txt","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define sq(x) ((x)*(x))

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace __gnu_pbds;
using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<int,int> pii;


#define log 20
#define mod 1000000007LL
#define INF 1000000000000000000LL
#define maxn 2000005

const long double eps = 1e-9 ;

int main()
{
    int tc, t=1 ;

    scanf("%d",&tc) ;

    while( t++ <= tc )
    {
        int n ;

        scanf("%d",&n) ;

        multiset< pair<int,int> > leaf , nonleaf ;

        for(int i=1 ; i<=n ; i++)
        {
            int d ;
            scanf("%d",&d) ;
            if( d==1 ) leaf.insert( mp(0,d) ) ;
            else nonleaf.insert(mp(0,d)) ;
        }

        if(n==2)
        {
            printf("1\n") ;
            continue ;
        }
        else{
            printf("%d\n" , min(n/2, (int)nonleaf.size() ) ) ;
            continue ;
        }

        int ans = 0 ;

        while( nonleaf.size() > 0 )
        {
       //     for( auto l:leaf ) printf("(%d,%d)",l.xx,l.yy) ;
       //     printf("   %d\n",nonleaf.size() ) ;

            auto itleaf = leaf.begin() ;
            int mat = itleaf->xx ;
            leaf.erase(itleaf) ;

            if( mat == 1 )
            {
                auto itnonleaf = nonleaf.end() ;
                itnonleaf-- ;
                pair<int,int> p = *itnonleaf ;
                nonleaf.erase(itnonleaf) ;

                p.yy-- ;
                if( p.yy==1 ) leaf.insert( p ) ;
                else nonleaf.insert(p) ;
            }
            else{
                auto itnonleaf = nonleaf.begin() ;
                pair<int,int> p = *itnonleaf ;
                nonleaf.erase(itnonleaf) ;

                if( p.xx == 0 )
                {
                    p.xx = 1 ;
                    ans++ ;
                }
                p.yy-- ;
                if( p.yy==1 ) leaf.insert( p ) ;
                else nonleaf.insert(p) ;
            }
        }

        auto it1 = leaf.begin() ;
        auto it2 = it1 ;
        it2++ ;

        if( it1->yy == 0 && it2->yy == 0 ) ans++ ;

        printf("%d\n",ans) ;
    }

    return 0 ;
}

// problem - J
#include <bits/stdc++.h>
using namespace std;

#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r) {
    return uniform_int_distribution<int>(l, r) (rng);
}


const int N = 1e6+100;
const int mod = 998244353;

vector<int> g[N];
bool vis[N];
int depth[N];
int ans;
int odd = 0, even = 0;

void dfs(int u, int p) {
    vis[u] = true;
    depth[u] = depth[p] + 1;
    for(int v : g[u]) {
        if(!vis[v]) {
            dfs(v, u);
        }
        else {
            if(v != p && depth[v] < depth[u]) {
                int parity = (depth[u] - depth[v] + 1) & 1;
                if(parity) odd++;
                else even++;
            }
        }
    }
}

vector<pair<int,int>> edges;
int edge_val[N];
int F[N];
int brute_ans;
int n, m;

void bktk(int pos) {
    if(pos == edges.size()) {
        bool ok = true;
        for(int i = 1; i <= n; i++) {
            if(F[i]%5 != 0) ok = false;
        }
        if(ok) {
//            cout << "ways: " << endl;
//            for(int i = 0; i < m; i++) {
//                cout << edges[i].first << " " << edges[i].second << " -> " << edge_val[i] << endl;
//            }
//            for(int i = 1; i <= n; i++) {
//                cout << i << " -> " << F[i] << endl;
//            }
        }
        brute_ans += ok;
        return;
    }
    int u = edges[pos].first, v = edges[pos].second;
    for(int k = 0; k < 5; k++) {
        edge_val[pos] = k;
        bktk(pos+1);
        F[u]++;
        F[v]++;
    }
}

int bm(int b, int p) {
    if(p == 0) return 1;
    int t = bm(b, p/2);
    t = 1ll * t * t % mod;
    if(p & 1) return 1ll * t * b % mod;
    return t;
}

int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tc;
    cin >> tc;
    set<int> all;

    while(tc--) {
//        n = my_rand(2, 6);
//        m = min(n * (n-1) /2, my_rand(0, 12));
        cin >> n >> m;
        for(int i = 1; i <= n; i++) {
            g[i].clear();
            vis[i] = false;
            depth[i] = 0;
        }
        edges.clear();
        set<pair<int,int>> sss;
        for(int i = 0; i < m; i++) {
            int u, v;
//            u = my_rand(1, n);
//            v = my_rand(1, n);
//            if(u > v) swap(u, v);
            cin >> u >> v;
//            if(sss.count({u, v}) or u == v) {
//                i++;
//                continue;
//            }
//            sss.insert({u, v});
            g[u].push_back(v);
            g[v].push_back(u);
            edges.push_back({u, v});
        }
//        brute_ans = 0;
//        for(int i = 1; i <= n; i++) F[i] = 0;
//        bktk(0);
//        vector<int> pw(n + 1);
//        pw[0] = 1;
//        for(int i = 1; i <= n; i++) {
//            pw[i] = 2*pw[i-1]%mod;
//        }
        int ans = 1;
        for(int i = 1; i <= n; i++) {
            if(!vis[i]) {
                odd = 0, even = 0;
                dfs(i, 0);
                int Rank = n-1;
                if(odd) Rank = n;
                int baki = n-1+even+odd-Rank;
                while(baki--) ans = 1ll * ans * 5 % mod;
            }
        }
//        assert(ans == brute_ans);
        cout << ans << "\n";
    }

}


 // problem F
#include<bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3e5+7;
const long long INF = 1e18;
int a[N];
LL tr[4*N];
LL lz[4*N];

///2. Push lazy down and merge lazy
void propagate(int u, int st, int en) {
    tr[u] += lz[u];
    if (st!=en) {
        lz[2*u] += lz[u];
        lz[2*u+1] += lz[u];
    }
    lz[u] = 0;
}


void update(int u, int st, int en, int l, int r, LL x) {
    propagate(u, st, en);
    if (r<st || en<l)  return;
    else if (l<=st && en<=r) {
        lz[u] += x;             ///4. Merge lazy
        propagate(u, st, en);
    }
    else {
        int mid = (st+en)/2;
        update(2*u, st, mid, l, r, x);
        update(2*u+1, mid+1, en, l, r, x);
        tr[u] = min(tr[2*u], tr[2*u+1]);
    }
}

LL query(int u, int st, int en, int l, int r) {
    propagate(u, st, en);
    if (r<st || en<l)  return INF;        /// 5. Proper null value
    else if (l<=st && en<=r)    return tr[u];
    else {
        int mid = (st+en)/2;
        return min(query(2*u, st, mid, l, r), query(2*u+1, mid+1, en, l, r));
    }
}

void debug(int u, int st, int en) {
    cout<<"--->"<<u<<" "<<st<<" "<<en<<" "<<tr[u]<<" "<<lz[u]<<endl;
    if (st==en) return;
    int mid = (st+en)/2;
    debug(2*u, st, mid);
    debug(2*u+1, mid+1, en);
}


int x[N], y[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, a, b;
    cin>>n>>a>>b;

    vector<int> v;
    update(1,0,n,0,n,1);

    for (int i=1; i<=n; i++) {
        int h;
        cin>>h;

        x[i] = (h-1)/b;
        int left = h - x[i]*b;
        assert(left > 0);
        y[i] = (left+a-1)/a;

        v.push_back(i);

        update(1,0,n,i,n,x[i]+1);
    }

    sort(v.begin(), v.end(), [](int a, int b) {return y[a] == y[b] ? a > b : y[a] < y[b];});

    int ans = 0;
    for (int i=0; i<n; i++) {
        int idx = v[i];
        update(1,0,n,idx,n,-x[idx]-1);
        update(1,0,n,idx,n,x[idx]-y[idx]);
        int z = query(1,0,n,0,n);
        if (z < 0) {
            update(1,0,n,idx,n,x[idx]+1);
            update(1,0,n,idx,n,-x[idx]+y[idx]);
        }
        else ans++;
    }
    cout<<ans<<endl;
}

// problem - E

#include <bits/stdc++.h>
using namespace std;

#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r) {
    return uniform_int_distribution<int>(l, r) (rng);
}


int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x] ^= 1;
    }
    vector<bool> good(n+1);

    vector<int> piles;
    for(int i = 1; i <= n; i++) if(a[i]) piles.push_back(i);
//    debug(), dbg(piles);
    if(piles.size() <= 500) {
        for(int x = 1; x <= n; x++) {
            int cnt = 0;
            for(int y : piles) {
                int z = y%(x+1);
//                debug(), dbg(y), dbg(z);
                cnt ^= z;
            }
//            debug(), dbg(cnt);
            if(cnt) good[x] = true;
        }
        for(int i = 1; i <= n; i++) {
            if(good[i]) cout << "Alice ";
            else cout << "Bob ";
        }
        return 0;
    }

    for(int i = 1; i <= n; i++) {
        a[i] ^= a[i-1];
    }
    for(int k = 18; k >= 0; k--) {
        for(int i = 1; i <= n; i++) {
            if(good[i]) continue;
            int x = i+1;
            int cnt = 0;
            int sz = (1<<k);
            for(int l = 0; l <= n; l += x) {
                int r = min(l+x-1, n);
                for(int bl = l+sz; bl <= r; bl += (sz<<1)) {
                    int br = min(r, bl+sz-1);
                    cnt ^= a[br]^a[bl - 1];
                }
            }
            if(cnt) good[i] = true;
        }
//        debug(), dbg(k), dbg(good);
    }
    for(int i = 1; i <= n; i++) {
        if(good[i]) cout << "Alice ";
        else cout << "Bob ";
    }
}