In the 2050 Conference, some people from the competitive programming community meet together and are going to take a photo. The n people form a line. They are numbered from 1 to n from left to right. Each of them either holds a cardboard with the letter 'C' or a cardboard with the letter 'P'.

Let C=\\{c_1,c_2,...,c_m\} (c_1<c_2<… <c_m) be the set of people who hold cardboards of 'C'. Let P=\\{p_1,p_2,...,p_k\} (p_1<p_2<… <p_k) be the set of people who hold cardboards of 'P'. The photo is good if and only if it satisfies the following constraints: 

  1. C∪ P=\{1,2,...,n\} 
  2. C∩ P =∅ . 
  3. c_i-c_{i-1}≤ c_{i+1}-c_i(1< i <m). 
  4. p_i-p_{i-1}≥ p_{i+1}-p_i(1< i <k). 



Given an array a_1,…, a_n, please find the number of good photos satisfying the following condition: $$$∑_{x∈ C} a_x < ∑_{y∈ P} a_y.$$$

The answer can be large, so output it modulo 998 244 353. Two photos are different if and only if there exists at least one person who holds a cardboard of 'C' in one photo but holds a cardboard of 'P' in the other.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 200 000). Description of the test cases follows.

The first line of each test case contains a single integer n (1≤ n≤ 200 000).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 200 000.

Output

For each test case, output the answer modulo 998 244 353 in a separate line.

Example

Input


3
5
2 1 2 1 1
4
9 2 2 2
1
998244353


Output


10
7
1

Note

For the first test case, there are 10 possible good photos satisfying the condition: PPPPP, CPPPP, PCPPP, CCPPP, PCCPP, PCPCP, PPPPC, CPPPC, PCPPC, PPPCC.

For the second test case, there are 7 possible good photos satisfying the condition: PPPP, PCPP, PCCP, PPPC, PCPC, PPCC, PCCC.
// Keep it simple
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define Br cout<<endl
#define int long long
#define fe first
#define se second
#define double long double
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define PT(x) cout << (x) << endl
#define last(x)  prev(x.end())
#define PP(x) cout << (x) << " "
#define PS(x) for(auto it: x)cout << it <<" "; cout << endl;
#define PTT(x) cout << (#x) << " is " << (x) << endl
#define lets_go ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
void PV(vi v) { for (int i = 0 ; i < (int)v.size() ; i++) cout << v[i] << " " ; cout << endl;}
void PVV(vii v) {for (int i = 0 ; i < (int)v.size() ; i++) cout << v[i].first << " " << v[i].second << endl;}
void PA(int v[], int n, int x = 0) { for (int i = x ; i < n + x; i++)cout << v[i] << ' ' ; cout << endl;}
void IN(int a[], int n, int x = 0) {for (int i = x; i < n + x; i++)cin >> a[i];}
inline void op() {
#ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
}

// <=================================================================================================================================
// <=================================================================================================================================
const int M = 998244353;
const int IM = 1e18 + 37;
const int N = 2e5 + 10;

int a[N];
int pre[N], suf[N];
int lf[N], rt[N]; // left odd , left even
signed  main() {
   lets_go
   op();

   int t;
   cin >> t;
   while (t--) {
      int n;
      cin >> n;
      int s = 0;
      for (int i = 0; i <= n + 1; i++)
         pre[i] = a[i] = suf[i] = lf[i] = rt[i] = 0;

      for (int i = 1; i <= n; i++) {
         cin >> a[i];
         s += a[i];
         pre[i] += pre[i - 1] + a[i];
         if (i % 2)
            lf[i] += a[i];
         else
            rt[i] += a[i];
         rt[i] += rt[i - 1];
         lf[i] += lf[i - 1];
      }
      // too many cases
      int ans = 1; // ppppppppp
      for (int i = 1, c = 0; i <= n; i++) {
         c += a[i];
         if (c < s - c)
            ans = (ans+1)%M;
         int l = 1, r = (n - i) / 2;
         int end = -1;
         while (l <= r) {
            int mid = (l + r) / 2;
            if (i % 2) {
               if (lf[i + mid * 2] - lf[i] + c < s - c - (lf[i + mid * 2] - lf[i]) ) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
            else {
               if (rt[i + mid * 2] - rt[i] + c < s - c - (rt[i + mid * 2] - rt[i])) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
         }
         if (end != -1)
            ans = (ans + (end - i) / 2)%M;
         if (end == n)
            ans = (ans - 1 + M)%M;
         l = 1, r = (n - 2 - i) / 2;
         end = -1;
         c += a[n];
         if (c < s - c && i <= n - 2)
            ans++;
         while (l <= r) {
            int mid = (l + r) / 2;
            if (i % 2) {
               if (lf[i + mid * 2] - lf[i] + c < s - c - (lf[i + mid * 2] - lf[i]) ) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
            else {
               if (rt[i + mid * 2] - rt[i] + c < s - c - (rt[i + mid * 2] - rt[i])) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
         }
         //PV({i,c,end}); //-------------
         if (end != -1)
            ans = ((end - i) / 2 + ans)%M;

         c -= a[n];
      }
      //PTT(ans);
      for (int i = 2, c = 0; i <= n; i++) {
         c += a[i];
         if (c < s - c)
            ans = (ans+1)%M;
         int l = 1, r = (n - i) / 2;
         int end = -1;
         while (l <= r) {
            int mid = (l + r) / 2;
            if (i % 2) {
               if (lf[i + mid * 2] - lf[i] + c < s - c - (lf[i + mid * 2] - lf[i]) ) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
            else {
               if (rt[i + mid * 2] - rt[i] + c < s - c - (rt[i + mid * 2] - rt[i])) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
         }
         if (end != -1)
            ans = (ans + (end - i) / 2)%M;
         if (end == n)
            ans = (ans - 1 + M)%M;
         l = 1, r = (n - 2 - i) / 2;
         end = -1;
         c += a[n];
         if (c < s - c && i <= n - 2)
            ans++;
         while (l <= r) {
            int mid = (l + r) / 2;
            if (i % 2) {
               if (lf[i + mid * 2] - lf[i] + c < s - c - (lf[i + mid * 2] - lf[i]) ) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
            else {
               if (rt[i + mid * 2] - rt[i] + c < s - c - (rt[i + mid * 2] - rt[i])) {
                  end = i + mid * 2;
                  l = mid + 1;
               }
               else
                  r = mid - 1;
            }
         }
         //PV({i,c,end}); //-------------
         if (end != -1)
            ans = ((end - i) / 2 + ans)%M;

         c -= a[n];
      }
      // PTT(ans);
      for (int i = n, c = 0; i > 2; i--) {
         c += a[i];
         if (s - c > c)
            ans++;
      }
      PT(ans%M);
   }



   return 0;
}
