#P1603C. Extreme Extension

    ID: 1630 Type: RemoteJudge 4000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 8 Uploaded By: Tags>dpgreedymathnumber theory*2300

Extreme Extension

Description

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

  • Select an index ii such that 1ib1 \le i \le |b|, where b|b| is the current length of bb.
  • Replace bib_i with two elements xx and yy such that xx and yy both are positive integers and x+y=bix + y = b_i.
  • This way, the array bb changes and the next operation is performed on this modified array.

For example, if b=[2,4,3]b = [2, 4, 3] and index 22 gets selected, then the possible arrays after this operation are [2,1,3,3][2, \underline{1}, \underline{3}, 3], [2,2,2,3][2, \underline{2}, \underline{2}, 3], or [2,3,1,3][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,2,2,3][2, 4, 3] \rightarrow [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 aa of nn integers. Help him find the sum of extreme values of all nonempty subarrays of aa modulo 998244353998\,244\,353. If a subarray appears in aa multiple times, its extreme value should be counted the number of times it appears.

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

The first line contains a single integer tt (1t100001 \le t \le 10\,000) — the number of test cases.

The first line of each test case contains a single integer nn (1n1051 \le n \le 10^5).

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1051 \le a_i \le 10^5).

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

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

Input

The first line contains a single integer tt (1t100001 \le t \le 10\,000) — the number of test cases.

The first line of each test case contains a single integer nn (1n1051 \le n \le 10^5).

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1051 \le a_i \le 10^5).

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

Output

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

Sample Input 1

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

Sample Output 1

5
9
0
117

Note

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

In the first test case,

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

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

  • f(1,2)=1f(1, 2) = 1, because [5,4][2,3,4][5, 4] \rightarrow [\underline{2}, \underline{3}, 4];
  • f(2,3)=1f(2, 3) = 1, because [4,3][1,3,3][4, 3] \rightarrow [\underline{1}, \underline{3}, 3];
  • f(1,1)=f(2,2)=f(3,3)=0f(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=5a = 3 + 1 + 1 + 0 + 0 + 0 = 5.