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

vector<int> solve(int N, vector<ll>& A, vector<pair<int, int>>& edges, int Q, vector<pair<ll, int>>& queries) {
    vector<vector<int>> adj(N + 1);
    for (auto& edge : edges) {
        int u = edge.first, v = edge.second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    auto toBinary = [](ll value) {
        string binary = bitset<62>(value).to_string();
        return binary;
    };

    vector<string> binaryValues(N + 1);
    for (int i = 1; i <= N; ++i) {
        binaryValues[i] = toBinary(A[i-1]);
    }

    vector<vector<int>> ancestors(N + 1);
    vector<int> parent(N + 1, -1);

    function<void(int, int)> dfs = [&](int node, int par) {
        parent[node] = par;
        if (par != -1) {
            ancestors[node] = ancestors[par];
            ancestors[node].push_back(par);
        }
        for (int neighbor : adj[node]) {
            if (neighbor == par) continue;
            dfs(neighbor, node);
        }
    };

    dfs(1, -1);

    auto longestCommonPrefix = [](const string& a, const string& b) {
        int len = 0;
        while (len < a.size() && a[len] == b[len]) {
            ++len;
        }
        return len;
    };

    vector<int> ans;
    for (auto& query : queries) {
        ll V = query.first;
        int X = query.second;
        string V_binary = toBinary(V);

        int maxLength = 0;
        for (int ancestor : ancestors[X]) {
            int lcp = longestCommonPrefix(V_binary, binaryValues[ancestor]);
            maxLength = max(maxLength, lcp);
        }
        int lcp = longestCommonPrefix(V_binary, binaryValues[X]);
        maxLength = max(maxLength, lcp);

        ans.push_back(maxLength);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        vector<pair<int, int>> edges(N - 1);
        for (int i = 0; i < N - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edges[i] = {u, v};
        }
        int Q;
        cin >> Q;
        vector<pair<ll, int>> queries(Q);
        for (int i = 0; i < Q; ++i) {
            cin >> queries[i].first >> queries[i].second;
        }

        vector<int> results = solve(N, A, edges, Q, queries);
        for (int result : results) {
            cout << result << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(vector<ll>&a,ll k)
{
  ll n=a.size();
  ll s=0,st=0,en=0,maxsofar=0,maxend=0;
  for(ll i=0;i<n;i++)
  {
    maxend+=a[i];
    if(maxsofar<maxend)
    {
      maxsofar=maxend;
      st=s;
      en=i;
    }
    if(maxend<0)
    {
      maxend=0;
      s=i+1;
    }
  }
  return maxsofar+k*(en-st);
}
signed main() 
{
    ll n,k; cin>>n>>k;
  vector<ll>a(n);
  for(ll i=0;i<n;i++) cin>>a[i];
  cout<<solve(a,k);
    return 0;            
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
     int T;
    cin >> T;

    while (T--) {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> v(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    vector<pair<long long, long long>> a;
    for (int i = 0; i < n; i++) {
        long long x = 0;
        long long count = 0;
        for (int j = 0; j < m; j++) {
            if (v[i][j]) {
                x |= (1LL << j);
            } else {
                count++;
            }
        }
        a.push_back({x, count});
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long curr = 0;
        for (int j = 0; j < n; j++) {
            if (a[i].first == a[j].first) {
                curr++;
            }
        }
        if (a[i].second > k) {
            continue;
        }
        if ((k - a[i].second) % 2 == 1) {
            continue;
        }
        ans = max(ans, curr);
    }
    cout << ans << endl;
}
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}