#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int cnt1 = 0;
    for (int i = 0; i < n; ++i) {
      int x;
      cin >> x;
      cnt1 += (x == 1);
    }
    cout << n - cnt1 / 2 << '\n';
  }
}

for _ in range(int(input())):
    a1, a2, a3, a4 = map(int, input().split())
    if a1 == 0:
        print(1)
    else:
        print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) {
      int x;
      cin >> x;
      pos[x] = i;
    }
    int l = (n + 1) / 2, r = (n + 2) / 2;
    while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) {
      --l;
      ++r;
    }
    cout << (n - r + l + 1) / 2 << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

int get(const vector<int> &a, const vector<int> &b){
	int res = 0;
	while (res < int(a.size()) && a[res] == b[res])
		++res;
	return res;
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<vector<int>> a(n, vector<int>(m));
		forn(i, n) forn(j, m){
			scanf("%d", &a[i][j]);
			--a[i][j];
		}
		vector<vector<int>> b(n, vector<int>(m));
		forn(i, n) forn(j, m) b[i][a[i][j]] = j;
		sort(b.begin(), b.end());
		forn(i, n){
			int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
			int ans = 0;
			if (j > 0) ans = max(ans, get(a[i], b[j - 1]));
			if (j < n) ans = max(ans, get(a[i], b[j]));
			printf("%d ", ans);
		}
		puts("");
	}
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n;
li m1, m2;

inline bool read() {
	if(!(cin >> n >> m1 >> m2))
		return false;
	return true;
}

vector<pt> mFact;
vector<li> divs;

void factM(li m1, li m2) {
	mFact.clear();

	for (int d = 2; d * d <= m1 || d * d <= m2; d++) {
		int cnt = 0;
		while (m1 % d == 0) {
			m1 /= d;
			cnt++;
		}
		while (m2 % d == 0) {
			m2 /= d;
			cnt++;
		}
		if (cnt > 0)
			mFact.push_back({d, cnt});
	}
	if (m1 > m2)
		swap(m1, m2);
	if (m1 > 1)
		mFact.push_back({m1, 1});
	if (m2 > 1) {
		if (m2 == m1)
			mFact.back().y++;
		else
			mFact.push_back({m2, 1});
	}
}

void genDivisors(int pos, li val) {
	if (pos >= sz(mFact)) {
		divs.push_back(val);
		return;
	}
	li cur = val;
	fore (pw, 0, mFact[pos].y + 1) {
		genDivisors(pos + 1, cur);
		if (pw < mFact[pos].y)
			cur *= mFact[pos].x;
	}
}

inline void solve() {
	factM(m1, m2);

	divs.clear();
	genDivisors(0, 1);
	sort(divs.begin(), divs.end());

	vector<int> ans(sz(divs), 0);

	vector<li> dp(sz(divs), -1);
	fore (id, 0, sz(divs)) {
		if (divs[id] <= n)
			dp[id] = divs[id];
		for (auto [p, pw] : mFact) {
			if (divs[id] % p != 0)
				continue;
			
			int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin());
			dp[id] = max(dp[id], dp[pos]);
		}

		if (divs[id] / dp[id] <= n)
			ans[id] = divs[id] / dp[id];
	}

	int cnt = 0;
	int xorSum = 0;
	fore (i, 0, sz(ans)) {
		cnt += ans[i] > 0;
		xorSum ^= ans[i];
	}
	
//	cout << sz(ans) << endl;
//	cout << ans << endl;
	cout << cnt << " " << xorSum << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);

	int t; cin >> t;
	
	while (t--) {
		
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int varMul(int x)
{
    return x;
}

template<typename... Args>
int varMul(int x, Args... args)
{
    return mul(x, varMul(args...));
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

vector<int> fact, rfact;
vector<int> dp;
int n;

void precalc()
{
    fact.resize(n + 1);
    rfact.resize(n + 1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = mul(i, fact[i - 1]);
    for(int i = 0; i <= n; i++)
        rfact[i] = binpow(fact[i], MOD - 2);
    dp.resize(n + 1, -1);
}

int C(int n, int k)
{
    if(n < 0 || n < k || k < 0) return 0;
    return varMul(fact[n], rfact[k], rfact[n - k]);
}

int calc(int x)
{
    if(dp[x] != -1) return dp[x];
    if(x == 1) return dp[x] = 1;
    if(x == 2) return dp[x] = 1;
    dp[x] = 0;
    int& d = dp[x];
    for(int i = 1; i < x; i++)
    {
        d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1)));
    }   
    return d;
}

int main()
{
    cin >> n;
    precalc();
    cout << add(mul(calc(n), 2), -2) << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int LOGN = 18;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;

#define forn(i, n) for(int i = 0; i < int(n); i++)

inline int mul(int a, int b)
{
    return (a * 1ll * b) % MOD;
}

inline int norm(int a) 
{
    while(a >= MOD)
        a -= MOD;
    while(a < 0)
        a += MOD;
    return a;
}

inline int binPow(int a, int k) 
{
    int ans = 1;
    while(k > 0) 
    {
        if(k & 1)
            ans = mul(ans, a);
        a = mul(a, a);
        k >>= 1;
    }
    return ans;
}

inline int inv(int a) 
{
    return binPow(a, MOD - 2);
}

vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];

void precalc() 
{
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, 1);
        iw[st].assign(1 << st, 1);
        
        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int ibw = inv(bw);
        
        int cw = 1;
        int icw = 1;
        
        for(int k = 0; k < (1 << st); k++) 
        {
            w[st][k] = cw;
            iw[st][k] = icw;
            
            cw = mul(cw, bw);
            icw = mul(icw, ibw);
        }
        
        rv[st].assign(1 << st, 0);
        
        if(st == 0) 
        {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(int a[N], int n, int ln, bool inverse) 
{   
    for(int i = 0; i < n; i++) 
    {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }
    
    for(int st = 0; (1 << st) < n; st++) 
    {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) 
        {
            for(int pos = k; pos < k + len; pos++) 
            {
                int l = a[pos];
                int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
                
                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) 
    {
        int in = inv(n);
        for(int i = 0; i < n; i++)
            a[i] = mul(a[i], in);
    }
}

int aa[N], bb[N], cc[N];

vector<int> multiply(vector<int> a, vector<int> b) 
{
    int sza = a.size();
    int szb = b.size();
    int n = 1, ln = 0;
    while(n < (sza + szb))
        n <<= 1, ln++;
    for(int i = 0; i < n; i++)
        aa[i] = (i < sza ? a[i] : 0);
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : 0);
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = mul(aa[i], bb[i]);
        
    fft(cc, n, ln, true);
    
    int szc = n;
    vector<int> c(szc);
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
    return c;
}                    

int main()
{
    int n;
    cin >> n;
    vector<int> fact(n + 1);
    fact[0] = 1;
    for(int i = 0; i < n; i++)
        fact[i + 1] = mul(fact[i], i + 1);
    precalc();
    vector<int> A = {0, 1, 2};
    vector<int> B = {0, 1, 1};
    vector<int> C = {0, 1, 1};
    vector<int> D = {0, 1, 1};
    vector<int> conv;
    const int K = 2000;
    int last_conv = -1e9;
    while(A.size() <= n)
    {
        int cur = A.size();
        if(cur - last_conv >= K)
        {
            last_conv = cur - 1;
            conv = multiply(C, D);
        }
        /*for(auto x : conv) cerr << x << " ";
        cerr << endl;*/
        int val_A;
        if(last_conv * 2 >= cur)
        {
            val_A = conv[cur];
            // [cur - last_conv, last_conv] are already used
            for(int i = 1; i < (cur - last_conv); i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
            for(int i = last_conv + 1; i < cur; i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
        }
        else
        {
            val_A = 0;
            for(int i = 1; i <= cur - 1; i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
        }
        val_A = mul(val_A, fact[cur - 1]);
        val_A = mul(val_A, 2);
        A.push_back(val_A);
        B.push_back(mul(val_A, inv(2)));
        C.push_back(mul(val_A, inv(fact[cur])));
        D.push_back(mul(B.back(), inv(fact[cur - 1])));
    }
    cout << norm(A[n] - 2) << endl;
}