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.
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
#define forn(i, j, k) for(auto i=j;i<k;i++)
#define Forn(i, j, k) for(auto i=j;i>k;i--)
#ifdef XYL_DEBUG
#define debug(x) cerr<<(#x)<<" : "<<(x)<<' '
#define debugArr(x, i, n) cerr<<(#x)<<" : ";forn(_,i,n)cerr<<x[_]<<' '
#else
#define debug(x) 0
#define debugArr(x,i,n) 0
#endif
#define numb (ch^'0')
#define mk make_pair
#define pb push_back
#define read(v, i) forn(_,0,i)rd(v[_])
#define opt(x) (x<0?putchar('-'),output(-x):output(x))
typedef long long ll;

template<class T>
void rd(T &x) {
    char ch;
    x = 0;
    bool fl = false;
    while (!isdigit(ch = getchar()))(ch == '-') && (fl = true);
    for (x = numb; isdigit(ch = getchar()); x = x * 10 + numb);
    (fl == true) && (x = -x);
}

template<class T>
void output(T x) {
    if (x / 10)output(x / 10);
    putchar(x % 10 + '0');
}

template<class T>
void ot(T x, int n) {
    forn(i, 0, n)i ? putchar('\n') : 0, opt(x[i]);
}

namespace Modulo {
    using type = int;

    const type mod = 998244353;

    type ad(type x, type y) { return x + y >= mod ? x + y - mod : x + y; }

    type sub(type x, type y) { return ad(x, mod - y); }

    type mul(type x, type y) { return 1LL * x * y % mod; }

    void inc(type &x, type y) { x = ad(x, y); }

    void inc2(type &x, type y) { x = mul(x, y); }

    type qm(type x, type y = mod - 2) {
        type ret = 1;
        while (y) {
            if (y & 1) ret = mul(x, ret);
            x = mul(x, x);
            y >>= 1;
        }
        return ret;
    }

    type div(type x, type y) { return mul(x, qm(y)); }

    template<class ...Args>
    type ad(type a, type b, Args ...args) { return ad(ad(a, b), args...); }

    template<class ...Args>
    type mul(type a, type b, Args ...args) { return mul(mul(a, b), args...); }
}

ll gcd(ll i, ll j) {
    return !j ? i : gcd(j, i % j);
}

ll lcm(ll i, ll j) {
    return i / gcd(i, j) * j;
}

using namespace Modulo;
gp_hash_table<int, int> mpp[100007];
int arr[100007];
int n;

int dfs(int i, int j) {
    if (i < 0)return 0;
    if (mpp[i][j]!=0)return mpp[i][j];
    if (arr[i] % j == 0)return mpp[i][j] = ad(dfs(i - 1, j), mul(arr[i] / j - 1, i + 1));
    int tm = arr[i] / j + 1;
    return mpp[i][j] = ad(dfs(i - 1, arr[i] / tm), mul(tm - 1, i + 1));
}
gp_hash_table<int, int>tmp;
void solve() {
    rd(n);
    read(arr, n);
    int ans = 0;
    Forn(i, n - 1, -1)ans = ad(ans, dfs(i, arr[i])),tmp = move(mpp[i]);
    opt(ans);
    putchar('\n');
}

signed main() {
    int t = 1;
    rd(t);
    for (int i = 1; i <= t; i++) {
        solve();
    }
    return 0;
}