#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const long long INF = 8e18;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x * f;
}
long long gcd(long long a, long long b) {
  long long res;
  while (b) {
    res = a % b;
    a = b;
    b = res;
  }
  return a;
}
long long qpow(long long a, long long b, const int mo) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mo;
    a = a * a % mo;
    b >>= 1;
  }
  return res;
}
long long qpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long slow_mul(long long a, long long b, long long k) {
  long long res = 0;
  while (b) {
    if (b & 1) res = (res + a) % k;
    a = a * 2 % k;
    b >>= 1;
  }
  return res;
}
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long res = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return res;
}
void init(const int mo = mod) {}
int n;
int a[maxn];
int dp[2][maxn];
vector<int> v[2];
void solve() {
  cin >> n;
  long long ans = 0;
  bool f = 1;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; f && i <= n; ++i) {
    if (a[i] < a[i + 1])
      continue;
    else
      f = 0;
  }
  if (f == 0) {
    int cur = 1;
    for (int i = n; i >= 1; --i, cur ^= 1) {
      v[cur].push_back(a[i]);
      dp[cur][a[i]] = 1;
      int last = a[i];
      for (int &x : v[cur ^ 1]) {
        int y = dp[cur ^ 1][x];
        int res = (a[i] + x - 1) / x;
        int st = a[i] / res;
        ans += (long long)(res - 1) * y * i;
        dp[cur][st] += y;
        if (last != st) {
          v[cur].push_back(st);
          last = st;
        }
      }
      for (int &x : v[cur ^ 1]) dp[cur ^ 1][x] = 0;
      v[cur ^ 1].clear();
      if (ans >= MOD) ans %= MOD;
    }
  }
  cout << ans << '\n';
  for (int &x : v[0]) dp[0][x] = 0;
  for (int &y : v[1]) dp[1][y] = 0;
  v[0].clear();
  v[1].clear();
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int _ = 1;
  cin >> _;
  while (_-- > 0) solve();
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

For an array b of n integers, the extreme value of this array is the minimum number of times (possibly, zero) the following operation has to be performed to make b non-decreasing: 

  * Select an index i such that 1 ≤ i ≤ |b|, where |b| is the current length of b. 
  * Replace b_i with two elements x and y such that x and y both are positive integers and x + y = b_i. 
  * This way, the array b changes and the next operation is performed on this modified array. 



For example, if b = [2, 4, 3] and index 2 gets selected, then the possible arrays after this operation are [2, \underline{1}, \underline{3}, 3], [2, \underline{2}, \underline{2}, 3], or [2, \underline{3}, \underline{1}, 3]. And consequently, for this array, this single operation is enough to make it non-decreasing: [2, 4, 3] → [2, \underline{2}, \underline{2}, 3].

It's easy to see that every array of positive integers can be made non-decreasing this way.

YouKn0wWho has an array a of n integers. Help him find the sum of extreme values of all nonempty subarrays of a modulo 998 244 353. If a subarray appears in a multiple times, its extreme value should be counted the number of times it appears.

An array d is a subarray of an array c if d can be obtained from c by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5).

It is guaranteed that the sum of n over all test cases doesn't exceed 10^5.

Output

For each test case, print a single integer — the sum of extreme values of all subarrays of a modulo 998 244 353.

Example

Input


4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163


Output


5
9
0
117

Note

Let f(l, r) denote the extreme value of [a_l, a_{l+1}, …, a_r].

In the first test case, 

  * f(1, 3) = 3, because YouKn0wWho can perform the following operations on the subarray [5, 4, 3] (the newly inserted elements are underlined):

[5, 4, 3] → [\underline{3}, \underline{2}, 4, 3] → [3, 2, \underline{2}, \underline{2}, 3] → [\underline{1}, \underline{2}, 2, 2, 2, 3];

  * f(1, 2) = 1, because [5, 4] → [\underline{2}, \underline{3}, 4];
  * f(2, 3) = 1, because [4, 3] → [\underline{1}, \underline{3}, 3];
  * f(1, 1) = f(2, 2) = f(3, 3) = 0, because they are already non-decreasing. 



So the total sum of extreme values of all subarrays of a = 3 + 1 + 1 + 0 + 0 + 0 = 5.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const long long INF = 8e18;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x * f;
}
long long gcd(long long a, long long b) {
  long long res;
  while (b) {
    res = a % b;
    a = b;
    b = res;
  }
  return a;
}
long long qpow(long long a, long long b, const int mo) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mo;
    a = a * a % mo;
    b >>= 1;
  }
  return res;
}
long long qpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long slow_mul(long long a, long long b, long long k) {
  long long res = 0;
  while (b) {
    if (b & 1) res = (res + a) % k;
    a = a * 2 % k;
    b >>= 1;
  }
  return res;
}
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long res = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return res;
}
void init(const int mo = mod) {}
int n;
int a[maxn];
int dp[2][maxn];
vector<int> v[2];
void solve() {
  cin >> n;
  long long ans = 0;
  bool f = 1;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; f && i <= n; ++i) {
    if (a[i] < a[i + 1])
      continue;
    else
      f = 0;
  }
  if (f == 0) {
    int cur = 1;
    for (int i = n; i >= 1; --i, cur ^= 1) {
      v[cur].push_back(a[i]);
      dp[cur][a[i]] = 1;
      int last = a[i];
      for (int &x : v[cur ^ 1]) {
        int y = dp[cur ^ 1][x];
        int res = (a[i] + x - 1) / x;
        int st = a[i] / res;
        ans += (long long)(res - 1) * y * i;
        dp[cur][st] += y;
        if (last != st) {
          v[cur].push_back(st);
          last = st;
        }
      }
      for (int &x : v[cur ^ 1]) dp[cur ^ 1][x] = 0;
      v[cur ^ 1].clear();
      if (ans >= MOD) ans %= MOD;
    }
  }
  cout << ans << '\n';
  for (int &x : v[0]) dp[0][x] = 0;
  for (int &y : v[1]) dp[1][y] = 0;
  v[0].clear();
  v[1].clear();
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int _ = 1;
  cin >> _;
  while (_-- > 0) solve();
  return 0;
}

```