Problem Statement

An integer sequence that satisfies the following condition is called a good sequence.

• It is possible to perform the following merge operation zero or more times to make the sequence length 1.
  • Choose a location where two consecutive elements have equal values. Let x be the value of those elements. Remove both elements and insert x+1 at the location where the elements were.
    For example, if we perform a merge operation on the 2nd and 3rd elements of the sequence (1, 3, 3, 5), the sequence after the operation will be (1, 4, 5).

There is a length-N integer sequence A = (A_1, A_2, \dots, A_N).
You can perform the following insertion operation zero or more times.

• Choose any integer x. Insert one x at any position in A (possibly the beginning or end).

What is the minimum number of insertion operations needed to make A a good sequence? For any N and A satisfying the constraints, it is possible to make A a good sequence with a finite number of insertion operations.

You are given T test cases; solve the problem for each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

4
3
4 2 2
1
1
5
1 3 5 4 2
10
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

Sample Output 1

1
0
6
1889132222

For the 1st test case, the sequence (4, 2, 2, 3) obtained by inserting 3 at the end of A is a good sequence because it can be reduced to length 1 by performing merge operations in the following steps.

• Remove the 2s at the 2nd and 3rd positions and insert 2+1=3. The sequence becomes (4, 3, 3).
• Remove the 3s at the 2nd and 3rd positions and insert 3+1=4. The sequence becomes (4, 4).
• Remove the 4s at the 1st and 2nd positions and insert 4+1=5. The sequence becomes (5).

It is impossible to make A a good sequence with fewer than one insertion operation, so the answer is 1.

Problem Statement

There is a shogi (Japanese chess) board with H rows and W columns, and one knight piece. The square at the i-th row from the top and j-th column from the left of the board is represented as (i-1, j-1). (Note that the values are shifted by 1.)
This board is a torus, meaning the top and bottom are connected, and the left and right are connected. A knight at (i, j) can move to ((i-2) \bmod H, (j-1) \bmod W) or ((i-2) \bmod H, (j+1) \bmod W). (Note that this is different from the knight in Standard chess.)

Moving the knight on the board to satisfy the following condition is called a tour.

• Initially, place the knight at (0, 0). Then, move the knight H \times W times so that the knight visits every square exactly once. Finally, the knight returns to (0, 0).

Find the number of tours modulo 998244353. Two tours are considered different if and only if there exists an integer i (1 \leq i \leq H\times W) such that the destination of the i-th move is different.

Constraints

• 3 \leq H \leq 2 \times 10^5
• 3 \leq W \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 3

Sample Output 1

6

For example, the movement (0,0) \to (1,1) \to (2,2) \to (0,1) \to (1,2) \to (2,0) \to (0,2) \to (1,0) \to (2,1) \to (0,0) satisfies the conditions as a tour.
There are six tours in total.

Sample Input 2

123 45

Sample Output 2

993644157

Sample Input 3

6789 200000

Sample Output 3

152401277

Problem Statement

For a positive integer n, define R_n as "the integer obtained by interpreting a string of n consecutive 1s as a decimal number". For example, R_3 = 111.

You are given a positive integer sequence A = (A_1, A_2, \dots, A_N).
For k = 1, 2, \dots, N, calculate \mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353. Here, \mathrm{LCM} is the function that calculates the least common multiple.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3
2 4 6

Sample Output 1

11
1111
11222211

For k=1, \mathrm{LCM}(11) \bmod 998244353 = 11.
For k=2, \mathrm{LCM}(11,1111) \bmod 998244353= 1111.
For k=3, \mathrm{LCM}(11,1111,111111) \bmod 998244353= 11222211.

Sample Input 2

1
200000

Sample Output 2

202819780

Sample Input 3

10
47718 21994 98917 104184 160670 190107 125377 29127 7017 177076

Sample Output 3

429620650
844699313
355160870
608402385
858856681
605347397
566966598
429324494
370941155
567238109

Problem Statement

There is a shogi (Japanese chess) board with H rows and W columns, and one king piece. The square at the i-th row from the top and j-th column from the left of the board is represented as (i, j).
Initially, the king is placed at (A, B). You perform the following operation exactly T times.

• Move the king to one of the eight adjacent squares of the current square. More precisely, if the king is at square (i, j), move the king to one of (i+1,j+1), (i+1,j), (i+1,j-1), (i,j+1), (i,j-1), (i-1,j+1), (i-1,j), (i-1,j-1). The king cannot leave the board.

Find the number, modulo 998244353, of operation sequences such that the king is at (C, D) after completing all T operations. Two operation sequences are considered different if and only if there exists an integer i (1 \leq i \leq T) such that the king's position after the i-th operation is different.

Constraints

• 2 \leq H \leq 3 \times 10^5
• 2 \leq W \leq 3 \times 10^5
• 1 \leq T \leq 3 \times 10^5
• 1 \leq A \leq H
• 1 \leq B \leq W
• 1 \leq C \leq H
• 1 \leq D \leq W
• All input values are integers.

Sample Input 1

3 4 3 2 1 3 4

Sample Output 1

5

There are five operation sequences that satisfy the conditions in the problem statement. The king's movements corresponding to each operation sequence are as follows.

• (2, 1) \to (1, 2) \to (2, 3) \to (3, 4)
• (2, 1) \to (2, 2) \to (2, 3) \to (3, 4)
• (2, 1) \to (2, 2) \to (3, 3) \to (3, 4)
• (2, 1) \to (3, 2) \to (2, 3) \to (3, 4)
• (2, 1) \to (3, 2) \to (3, 3) \to (3, 4)

Sample Input 2

202 123 456 20 25 7 20

Sample Output 2

167373259