Problem Statement

There is an H\times W grid of cells. Let (h,w) denote the cell at the h-th row from the top and the w-th column from the left. Furthermore, you are given a string S = S_1\cdots S_{H+W-2} of length H+W-2 consisting of D, R, and ?.

Initially, all cells are painted white. You may perform the following operation, which consists of three steps, any number of times:

1. Choose a string X = X_1\cdots X_{H+W-2} of length H+W-2 satisfying all of the following.
   • X consists of exactly H-1 Ds and W-1 Rs.
   • For each 1 \le i \le H+W-2, if S_i is D then X_i must also be D.
   • For each 1 \le i \le H+W-2, if S_i is R then X_i must also be R.
2. Stand on cell (1,1). Then for i=1,2,\ldots in order, move one cell in the direction indicated by X_i: if X_i is D, move down one cell; if X_i is R, move right one cell. It can be shown that if X satisfies the conditions in step 1, the destination cell always exists within the grid.
3. For every cell you visited in step 2 (including the starting and ending cells), if the cell is currently white, paint it black.

Find the maximum possible number of cells that can be painted black in total.

There are T test cases; solve each one.

Constraints

• 1\le T\le 2\times 10^5
• 2\le H,W\le 2\times 10^5
• T,H,W are integers.
• S is a string of length H+W-2 consisting of D, R, and ?.
• The number of Ds in S is at most H-1.
• The number of Rs in S is at most W-1.
• The sum of H+W over all test cases is at most 4\times 10^5.

Sample Input 1

4
4 5
D?DRR?R
4 5
DDRRDRR
4 5
???????
2 2
DR

Sample Output 1

12
8
20
3

For the first test case, by choosing X as DRDRRDR in the first operation and DDDRRRR in the second operation, you can paint 12 cells black.

Problem Statement

Define the score of a non-empty integer sequence x = (x_1, \ldots, x_n) as the number of elements of x that are strictly greater than the average of x.

That is, the score of x is the count of indices i satisfying x_i > \dfrac{x_1+\cdots+x_n}{n}.

You are given a length-N integer sequence A = (A_1, \ldots, A_N). Find the maximum score of a non-empty subsequence of A.

There are T test cases; solve each one.

Constraints

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

Sample Input 1

3
5
2 6 5 7 5
5
10 10 10 10 10
5
1 10 100 1000 10000

Sample Output 1

3
0
1

For the first test case, below are examples of subsequences, their averages, and their scores.

• x = (A_1) = (2): the average is 2, and the score is 0.
• x = (A_3,A_5) = (5,5): the average is 5, and the score is 0.
• x = (A_1,A_3,A_4,A_5) = (2,5,7,5): the average is \frac{19}{4}, and the score is 3.
• x = (A_1,A_2,A_3,A_4,A_5) = (2,6,5,7,5): the average is 5, and the score is 2.

Problem Statement

Let S be the set of all positive integers.

Process Q queries in order. The i-th query gives you an integer A_i not less than 2 and a positive integer B_i, so perform the following two steps in order.

1. Remove from S all elements that are multiples of A_i.
2. Print the B_i-th smallest element of S. It can be shown that under the given constraints, S contains at least B_i elements at this point.

Constraints

• 1\le Q\le 10^5
• 2\le A_i\le 10^9
• 1\le B_i\le 10^5
• All input values are integers.

Sample Input 1

5
5 10
6 1
6 10
9 10
123456789 111

Sample Output 1

12
1
14
16
178

When the elements of S are listed in ascending order, the beginning of the list evolves as follows.

• Initially, S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace.
• The first query removes multiples of 5, resulting in S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace.
• The second query removes multiples of 6, resulting in S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
• The third query removes multiples of 6, resulting in S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
• The fourth query removes multiples of 9, resulting in S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.
• The fifth query removes multiples of 123456789, resulting in S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.

Problem Statement

You are given an N\times N matrix A = (A_{i,j}) (1\le i,j\le N) whose entries are 0 or 1.

Find, modulo 998244353, the number of trees G on N vertices numbered 1 to N that satisfy the following condition.

• A_{i,j}=1 if and only if at least one of the following holds:
  • When G is rooted at vertex 1, Vertex j is an ancestor of vertex i. That is, vertex j lies on the unique path in G between vertices 1 and i.
  • When G is rooted at vertex 1, Vertex i is an ancestor of vertex j. That is, vertex i lies on the unique path in G between vertices 1 and j.

Here, the endpoints of a path are considered to be on that path. Note that G being a tree guarantees uniqueness of the path between any two vertices.

There are T test cases; solve each one.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 400
• A_{i,j}\in \lbrace 0,1\rbrace (1\leq i,j\leq N)
• A_{i,i}=1 (1\leq i\leq N)
• A_{i,j}=A_{j,i} (1\leq i,j\leq N)
• The sum of N^2 over all test cases is at most 400^2.

Sample Input 1

5
3
1 1 1
1 1 0
1 0 1
3
1 1 1
1 1 1
1 1 1
3
1 0 0
0 1 0
0 0 1
3
1 0 1
0 1 1
1 1 1
7
1 1 1 1 1 1 1
1 1 0 1 0 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 1 0 1 0 1 1

Sample Output 1

1
2
0
0
8

In the first test case, the following one tree G satisfies the condition:

In the second test case, the following two trees G satisfy the condition:

Problem Statement

You are given positive integers N, H, and W, with H,W \le 3N-1.

Find the number, modulo 998244353, of ways to place four N\times N square tiles on an H\times W grid that satisfy all of the following conditions.

• Each tile exactly covers N^2 cells of the grid.
• No cell is covered by more than one tile.

Here, the tiles are indistinguishable.

There are T test cases; solve each one.

Constraints

• 1\le T\le 2\times 10^5
• 1\le N,H,W\le 10^9
• H,W\le 3N-1
• All input values are integers.

Sample Input 1

4
2 4 5
2 5 5
1000 1000 1000
1000 2222 2025

Sample Output 1

9
79
0
262210557

For the first test case, there are 9 ways as illustrated in the following figure: