Problem Statement

Takahashi decided to hold a tournament that lasts for 10^9 days in a single-elimination format.
There are 2^N players, called player 1, \ldots, player 2^N. Player i plans to participate from day l_i to day r_i of the tournament, for a total of r_i - l_i + 1 days.

First, we describe the flow of the tournament. There are 2^N - 1 matches in total, corresponding one-to-one with the integer pairs (i, j) satisfying 1 \leq i \leq N and 1 \leq j \leq 2^{N - i}. In the match corresponding to (i, j), the following two players compete to decide the winner and the loser:

• If i = 1, players 2j - 1 and 2j
• If i \geq 2, the winners of the matches corresponding to (i - 1, 2j - 1) and (i - 1, 2j)

Each match can be completed immediately when all the matches necessary to determine the two players who will compete in it have been completed, and both players are currently participating in the tournament. In particular, a single player can participate in multiple matches on the same day.
The match corresponding to (N, 1) is called the final, and the goal of the tournament is to complete it.

To successfully complete the final, Takahashi decided to perform the following manipulations:

• Instruct the referees to fix the outcomes of the matches as desired.
• Pay the players to change their participation schedules. To make player i participate from day l'_i to day r'_i, Takahashi needs to pay |l_i - l'_i| + |r_i - r'_i| yen. Here, l'_i and r'_i are integers satisfying 1 \leq l'_i \leq r'_i \leq 10^9.

Find the minimum total amount of money Takahashi needs to pay the players.

Constraints

• 1 \leq N \leq 18
• 1 \leq l_i \leq r_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 4
1 3
3 4
2 2
3 4
4 4
2 3
3 4

Sample Output 1

1

Assume that Takahashi pays 1 yen to player 4 to change his participation schedule to (l'_4, r'_4) = (2, 3), and not change the schedules of the other players. Then, for example, the final can be completed as follows:

1. On Day 1, conduct the match corresponding to (1, 1) (player 1 vs. player 2), and let player 2 win.
2. On Day 3, conduct the match corresponding to (1, 2) (player 3 vs. player 4), and let player 3 win.
3. On Day 3, conduct the match corresponding to (2, 1) (player 2 vs. player 3), and let player 3 win.
4. On Day 3, conduct the match corresponding to (1, 4) (player 7 vs. player 8), and let player 8 win.
5. On Day 4, conduct the match corresponding to (1, 3) (player 5 vs. player 6), and let player 5 win.
6. On Day 4, conduct the match corresponding to (2, 2) (player 5 vs. player 8), and let player 8 win.
7. On Day 4, conduct the match corresponding to (3, 1) (player 3 vs. player 8), and let player 8 win.

On the other hand, it is impossible to complete the final with less than 1 yen of payments. Therefore, the expected output is 1.

Sample Input 2

1
1 1
1000000000 1000000000

Sample Output 2

999999999

Sample Input 3

4
158260522 877914575
24979445 602436426
623690081 861648772
433933447 476190629
211047202 262703497
628894325 971407775
731963982 822804784
430302156 450968417
161735902 982631932
880895728 923078537
189330739 707723857
802329211 910286918
303238506 404539679
317063340 492686568
125660016 773361868
650287940 839296263

Sample Output 3

1088492036

Problem Statement

You are given N strings S_1, \ldots, S_N, each of length N, consisting only of 0 and 1. Let S_{i,j} denote the j-th character of S_i. It is guaranteed by the constraints that there exists at least one integer pair (i, j) satisfying S_{i,j} = 1.

Takahashi and Aoki play the following game:

1. Takahashi chooses one integer pair (i, j) satisfying 1 \leq i, j \leq N and S_{i,j} = 1.
2. Aoki asks Takahashi at least 0 and at most N questions. In each question, Aoki chooses an integer pair (i', j') satisfying 1 \leq i', j' \leq N, and Takahashi tells Aoki whether "At least one of i = i' or j = j' holds" is true or false.
3. Aoki guesses (i, j). If his guess is correct, Aoki wins; otherwise, he loses.

Aoki knows the possible choices of (i, j) that Takahashi can choose, that is, he knows S_1, \ldots, S_N before playing the game. Also, in step 2, Aoki can choose (i', j') based on the answers to previous questions.

Determine whether Aoki can always win the game regardless of Takahashi's choice of (i, j) and randomness, if he uses an appropriate strategy.

There are T test cases in each input.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 500
• The sum of N^2 over all test cases in each input is at most 500^2.
• S_i is a string of length N consisting of 0 and 1.
• There is at least one integer pair (i, j) satisfying S_{i,j} = 1.

Sample Input 1

3
2
01
11
2
11
11
10
0101011110
1100100001
1101100000
0111101010
1000011001
1110101010
1110110100
1110000110
0000001011
1001111100

Sample Output 1

Yes
No
Yes

In the first test case, an example of the game is as follows:

1. Takahashi chooses (i, j) = (2, 2) satisfying S_{i,j}=\ 1.
2. Aoki asks two questions. In the first question, he chooses (i', j') = (1, 1). Takahashi tells him that "At least one of i = 1 or j = 1 holds" is false. In the second question, he chooses (i', j') = (2, 2). Takahashi tells him that "At least one of i = 2 or j = 2 holds" is true.
3. Aoki guesses (i, j) = (2, 2). Since his guess is correct, Aoki wins.

This is just an example of the game, and Aoki's strategy might not be optimal. However, if Aoki uses an appropriate strategy, he can always win the game, so the output for the first test case is Yes.

Problem Statement

You are given two strings S and T of length N consisting of A and B. Let s_i denote the i-th character of S.

You can perform the following operation on S any number of times, possibly zero:

• Choose an integer pair (i, j) satisfying the following conditions:
  • 1 \leq i < j \leq N
  • s_i = s_j = A
  • s_{i+1} = s_{i+2} = \ldots = s_{j-1} = B
• Then, simultaneously replace each of s_i, s_{i+1}, \ldots, s_j with the other character (A becomes B, and B becomes A).

Determine the minimum number of operations required to make S equal to T. If it is impossible, print -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S and T are strings of length N consisting of A and B.

Sample Input 1

5
AAABA
BAAAB

Sample Output 1

2

You can make S equal to T in two operations as follows:

1. Perform the operation with (i, j) = (2, 3). S becomes ABBBA.
2. Perform the operation with (i, j) = (1, 5). S becomes BAAAB.

It is impossible to make S equal to T in fewer than two operations, so the answer is 2.

Sample Input 2

1
A
B

Sample Output 2

-1

It is impossible to make S equal to T. Note that you must choose (i, j) with i < j.

Sample Input 3

1
A
A

Sample Output 3

0

Without any operation, S is already equal to T.

Sample Input 4

10
AAABBABAAB
BBABBAAABB

Sample Output 4

7

Problem Statement

You are given an integer N and a prime P.

For a tree with N vertices labeled 1 through N, let a_i and b_i be the endpoints of the i-th edge (1 \leq i \leq N-1). Also, define x_j\ (1 \leq j \leq N-1) as:

• The number of integers i\ (1 \leq i \leq N-1) satisfying \min(a_i,b_i) \leq j \lt \max(a_i,b_i).

Find the number, modulo P, of sequences that could be (x_1, x_2, \ldots, x_{N - 1}).

Constraints

• 2 \leq N \leq 500
• 10^8 \leq P \leq 10^9
• P is prime.

Sample Input 1

3 998244353

Sample Output 1

3

There are three different trees with three vertices, if we distinguish the vertices by their labels but not the edges.
The corresponding (x_1, x_2) are (1, 1), (2, 1), and (1, 2), so the expected output is 3 modulo P = 998244353.

Sample Input 2

69 433416647

Sample Output 2

243082757

Find the count modulo P.

Problem Statement

You are given integers N, M, X, and Y.

Find the number, modulo 998244353, of pairs (A, B) of sequences A=(a_1,\ldots,a_N) and B=(b_1,\ldots,b_N) that satisfy all of the following conditions:

• A = (a_1, \ldots, a_N) is a sequence of non-negative integers.
• B = (b_1, \ldots, b_N) is a subsequence of (0, 1, \ldots, M - 1).
• \sum\limits_{i=1}^{N} a_i = X.
• \sum\limits_{i=1}^{N} a_i b_i = Y.

Constraints

• 1 \leq N \leq M \leq 2 \times 10^5
• 1 \leq X, Y \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 4 3 4

Sample Output 1

5

Here are the five pairs (A, B) satisfying the conditions:

• A = (0, 2, 1), B = (0, 1, 2)
• A = (1, 0, 2), B = (0, 1, 2)
• A = (1, 1, 1), B = (0, 1, 3)
• A = (1, 2, 0), B = (0, 2, 3)
• A = (2, 1, 0), B = (1, 2, 3)

Sample Input 2

1 1 1 1

Sample Output 2

0

There are no pairs (A, B) satisfying the conditions.

Sample Input 3

12345 67890 9876 54321

Sample Output 3

150392014

Find the count modulo 998244353.