Problem Statement

You are given positive integers N,A,B,C,D.

Find \displaystyle \sum_{i=1}^N \gcd (Ai+B,Ci+D), modulo 998244353. Here, \gcd(x,y) denotes the greatest common divisor of x and y.

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

Constraints

• 1\leq T\leq 200
• 1\leq N\leq 10^9
• 1\leq A,B,C,D\leq 10^4
• All input values are integers.

Sample Input 1

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

Sample Output 1

10
100000000
822404071

For the first test case, the answer is \gcd(4,6)+\gcd(5,10)+\gcd(6,14)+\gcd(7,18)=2+5+2+1=10.

Problem Statement

You are given a positive integer N and a prime P.

There is a length-N sequence A=(A_1,A_2,\ldots,A_N) where all elements are 0.

You can repeat the following operation any number of times, possibly zero:

• Choose a non-empty subset S of \lbrace 1,2,\ldots,N\rbrace. Let \displaystyle x=\sum_{i\in S}2^{i-1}. For each i\in S, replace A_i with x.

Find the number, modulo P, of possible sequences A after repeating the operations.

Constraints

• 1\leq N\leq 700
• P is a prime satisfying 10^8\lt P\lt 10^9.
• All input values are integers.

Sample Input 1

1 998244353

Sample Output 1

2

The possible sequences A are (0),(1), giving two possibilities.

Sample Input 2

2 998244353

Sample Output 2

7

The possible sequences A are (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3), giving seven possibilities.

Sample Input 3

3 998244353

Sample Output 3

57

Sample Input 4

4 998244353

Sample Output 4

1208

Sample Input 5

77 777777773

Sample Output 5

381787647

Problem Statement

You are given a positive integer N and a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N).

There is also a length-0 sequence of positive integers B.

You can perform the following operation between 0 and N times, inclusive.

• Remove the first or last element of A, and append that element to the beginning or end of B.

What is the maximum number of operations you can perform, given that B must be a strictly increasing sequence after the operations?

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

Constraints

• 1\le T\le 3\times 10^5
• 1\le N\le 3\times 10^5
• 1\le A_i \le N (1\leq i\leq N)
• The sum of N over all test cases is at most 3\times 10^5.
• All input values are integers.

Sample Input 1

3
5
3 1 4 1 5
3
2 2 1
16
3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2

Sample Output 1

4
2
11

For the first test case, consider performing the operations as follows.

• Remove the first element of A and append it to the end of B. Now A=(1,4,1,5),B=(3).
• Remove the first element of A and append it to the beginning of B. Now A=(4,1,5),B=(1,3).
• Remove the first element of A and append it to the end of B. Now A=(1,5),B=(1,3,4).
• Remove the last element of A and append it to the end of B. Now A=(1),B=(1,3,4,5).

The final B=(1,3,4,5) is a strictly increasing sequence, and the number of operations is 4. It is impossible to perform five operations while satisfying the condition, so the answer is 4.

For the second test case, note that B=(1,2,2) is not a strictly increasing sequence.

Problem Statement

You are given a positive integer N.

There is a complete binary tree with 2^N-1 vertices. The vertices are numbered 1 through 2^N-1.

Vertex 1 is the root, and for each i\ (1\leq i\lt 2^{N-1}), vertex i has vertices 2i and 2i+1 as its children.

Find one way to write an integer between 1 and 2^N-1, inclusive, on the vertices (where all 2^N-1 written integers are distinct) such that the following condition is satisfied.

• For each i\ (1\leq i\lt 2^{N-1}), the absolute difference between the sum of the integers written on the vertices of the subtree rooted at vertex 2i and the sum of the integers written on the vertices of the subtree rooted at vertex 2i+1 is 1.

It can be proved that there always exists a way to write the integers satisfying the condition under the constraints of this problem.

Constraints

• 2\leq N\leq 18
• All input values are integers.

Sample Input 1

3

Sample Output 1

1 7 2 3 4 5 6

We can verify that this assignment satisfies the condition, as follows.

• i=1: The sum of the integers written on the vertices of the subtree rooted at vertex 2 is 14, the sum of the integers written on the vertices of the subtree rooted at vertex 3 is 13, and |14-13|=1.
• i=2: The sum of the integers written on the vertices of the subtree rooted at vertex 4 is 3, the sum of the integers written on the vertices of the subtree rooted at vertex 5 is 4, and |3-4|=1.
• i=3: The sum of the integers written on the vertices of the subtree rooted at vertex 6 is 5, the sum of the integers written on the vertices of the subtree rooted at vertex 7 is 6, and |5-6|=1.

Problem Statement

You are given a positive integer N, a positive integer X, and a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N). Only X is given in binary, while N and the elements of P are given in decimal.

Determine whether there exist sequences of non-negative integers A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N) satisfying all of the following conditions.

• Both A and B are strictly increasing sequences.
• A_{P_i}=B_i \oplus X holds for i=1,2,\ldots,N.

Here, the binary operator \oplus denotes the bitwise XOR of non-negative integers.

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

Constraints

• 1\le T\le 10^5
• 2\le N\le 2\times 10^5
• 1\le X < 2^{10^6}
• P is a permutation of (1,2,\ldots,N).
• The sum of N over all test cases is at most 2\times 10^5.
• The sum of the number of digits of X in binary over all test cases is at most 10^6.
• T,N,P_i are given in decimal.
• X is given in binary without leading zeros.
• All input values are integers.

Sample Input 1

3
4
101
3 4 2 1
4
100
4 3 2 1
8
1101011
3 5 4 1 2 6 8 7

Sample Output 1

Yes
No
Yes

For the first test case, for example, A=(2,3,5,7) and B=(0,2,6,7) satisfy the conditions.