Với một dãy ~b~ gồm các số nguyên dương, ta định nghĩa "chi phí nới" của ~b~ là số lần ít nhất phải thực hiện thao tác sau để dãy trở thành không giảm:

• Chọn một chỉ số ~i~ ~(1 \le i \le |b|~, với ~|b|~ là độ dài hiện tại của dãy), rồi thay phần tử ~b_i~ bằng hai số nguyên dương ~x~ và ~y~ thỏa mãn ~x + y = b_i~. Sau thao tác, độ dài dãy tăng thêm ~1~ và thao tác kế tiếp thực hiện trên dãy mới.

Chẳng hạn với dãy ~b = \{2, 4, 3\}~, chọn ~i = 2~ có thể biến dãy thành ~\{2, 1, 3, 3\}~ hoặc ~\{2, 2, 2, 3\}~ hoặc ~\{2, 3, 1, 3\}~; chỉ cần một thao tác ~\{2, 4, 3\} \rightarrow \{2, 2, 2, 3\}~ là dãy đã trở thành không giảm, nên chi phí nới của nó bằng ~1~. Có thể chứng minh mọi dãy số nguyên dương đều có thể làm cho không giảm theo cách này.

Cho dãy ~a~ gồm ~n~ số nguyên. Hãy tính tổng chi phí nới của tất cả các dãy con liên tiếp khác rỗng của ~a~, lấy theo mô-đun ~998244353~. Một dãy con liên tiếp là dãy thu được bằng cách bỏ đi một số phần tử ở đầu và ở cuối của dãy ban đầu; nếu một dãy con xuất hiện nhiều lần thì chi phí nới của nó được cộng đúng bằng số lần nó xuất hiện.

Input

• Dòng đầu chứa số nguyên ~t~ ~(1 \le t \le 10^4)~ là số truy vấn cần trả lời;

• Mỗi truy vấn gồm hai dòng:

  • Dòng đầu truy vấn chứa số nguyên ~n~ ~(1 \le n \le 10^5)~;

  • Dòng thứ hai của truy vấn chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^5)~.

• Dữ liệu bảo đảm tổng của các ~n~ trên tất cả các truy vấn không vượt quá ~10^5~.

Output

Với mỗi truy vấn, in ra trên một dòng tổng chi phí nới của mọi dãy con liên tiếp, lấy theo mô-đun ~998244353~.

Scoring

Sample Input 1

3
3
5 4 3
1
69
4
3 2 1 4

Sample Output 1

5
0
9

Notes

Truy vấn thứ nhất, dãy ~\{5, 4, 3\}~:

• Chi phí nới của ~\{5, 4, 3\}~ là ~3~, của ~\{5, 4\}~ là ~1~, của ~\{4, 3\}~ là ~1~, còn ba dãy một phần tử đều có chi phí nới là ~0~;

• Tổng chi phí nới là: ~3 + 1 + 1 + 0 + 0 + 0 = 5~.

Truy vấn thứ hai: chỉ có một phần tử nên tổng chi phí nới bằng ~0~.

Truy vấn thứ ba, tổng chi phí nới là ~9~.