Problem Statement

Find the minimum value of a positive integer n satisfying the following two conditions.

• n is a multiple of K.
• In the decimal representation of n, 0 appears two or more times consecutively.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq K \leq 10^9
• All input values are integers.

Sample Input 1

3
17
6801
998244353

Sample Output 1

1003
34005
16970154001

This input contains three test cases.

For the first test case, the minimum value satisfying the conditions is 1003\ (= 17 \times 59).

For the second test case, the minimum value satisfying the conditions is 34005\ (= 6801 \times 5). Note that 20403\ (= 6801 \times 3) does not satisfy the condition.

For the third test case, the minimum value satisfying the conditions is 16970154001\ (= 998244353 \times 17). As this shows, the answer may not fit in a 32-bit integer.

Problem Statement

Let us place N square tiles of the same size on a plane so that they do not overlap.
Then, what is the maximum possible number of pairs of different tiles that share one full side?

Here, a pair of different tiles (a,b) is said to share one full side if and only if some side of a and some side of b coincide completely.

T test cases are given; solve each of them.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 10^{18}
• All input values are integers.

Sample Input 1

6
1
2
3
4
100000000000000000
1000000000000000000

Sample Output 1

0
1
2
4
199999999367544467
1999999998000000000

This input contains six test cases.

The figure below shows an example of an optimal arrangement of tiles for N=1,2,3,4.

• For the first test case, N=1.
  • There is no pair of different tiles sharing one full side.
• For the second test case, N=2.
  • The pair of tiles ({\rm a,b}) shares one full side.
• For the third test case, N=3.
  • The pairs of tiles ({\rm a,b}),({\rm b,c}) share one full side.
• For the fourth test case, N=4.
  • The pairs of tiles ({\rm a,b}),({\rm a,c}),({\rm b,d}),({\rm c,d}) share one full side.

Problem Statement

You are given a connected simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i-th edge connects vertices U_i and V_i.

Construct one integer sequence A=(A_1,A_2,\ldots,A_N) satisfying all of the following conditions.

• 0 \le A_v \le N for every vertex v.
• A_1=0.
• For every vertex v other than vertex 1, there is exactly one vertex w adjacent to v satisfying A_w=A_v-1.

It can be proved that under the constraints of this problem, there exists at least one integer sequence satisfying all of the above conditions. If there are multiple integer sequences satisfying the conditions, any of them will be accepted.

T test cases are given; solve each of them.

Constraints

• 1 \le T \le 3 \times 10^4
• 1 \le N \le 3 \times 10^5
• N-1 \le M \le 3 \times 10^5
• 1 \le U_i < V_i \le N
• (U_i,V_i) \neq (U_j,V_j) if i \neq j.
• The given graph is connected.
• The sum of N in each input is at most 3 \times 10^5.
• The sum of M in each input is at most 3 \times 10^5.
• All input values are integers.

Sample Input 1

3
6 7
1 5
1 3
3 5
2 5
3 4
3 6
4 6
1 0
6 10
4 6
1 4
2 5
3 6
1 3
1 2
2 3
2 4
3 4
3 5

Sample Output 1

0 2 1 2 1 2
0
0 3 2 1 3 3

This input contains three test cases.

For the first test case, consider setting A=(0,2,1,2,1,2).

• For vertex 1, A_1=0.
• For vertex 2, there is only one adjacent vertex w satisfying A_w=A_2-1, which is vertex 5.
• For vertex 3, there is only one adjacent vertex w satisfying A_w=A_3-1, which is vertex 1.
• For vertex 4, there is only one adjacent vertex w satisfying A_w=A_4-1, which is vertex 3.
• For vertex 5, there is only one adjacent vertex w satisfying A_w=A_5-1, which is vertex 1.
• For vertex 6, there is only one adjacent vertex w satisfying A_w=A_6-1, which is vertex 3.

Thus, this integer sequence A satisfies the conditions in the problem statement.

Additionally, setting A=(0,3,1,2,2,2) also satisfies the conditions, so the output 0 3 1 2 2 2 is also accepted.

The figure below shows, for each test case in the sample output, the vertex number v outside each vertex and A_v inside each vertex.

Problem Statement

There are N cards, numbered 1 through N. Initially, nothing is written on any of the cards.

You can write zero or more positive integers on each card.

The cost of writing a positive integer k once is equal to the number of digits in the decimal representation of k.

Determine whether it is possible to satisfy the following condition. If it is possible, output the minimum total cost required; if it is not possible, output -1.

• For every pair of positive integers (x,y) satisfying 1 \leq x < y \leq K, there exists a card containing exactly one of x and y.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^6
• 2 \leq K \leq 10^6
• The sum of N in each input is at most 10^6.
• The sum of K in each input is at most 10^6.
• All input values are integers.

Sample Input 1

4
3 5
100 25
5 1225
180 998244

Sample Output 1

5
39
-1
17655598

This input contains four test cases.

For the first test case, writing as follows satisfies the condition with a total cost of 5.

• Write 1, 5 on card 1.
• Write 2, 5 on card 2.
• Write 3 on card 3.

For the second test case, the minimum total cost required to satisfy the condition is 39.

For the third test case, it is impossible to satisfy the condition, so output -1.

For the fourth test case, the minimum total cost required to satisfy the condition is 17655598.

Problem Statement

You are given a string S consisting of A, B, and C.

You can perform the following operation zero or more times.

• Choose a substring (contiguous subsequence) of S that is A, AB, or ABC, and delete it. The remaining characters are concatenated, preserving their order.

Find the minimum possible length of S in the end.

T test cases are given; solve each of them.

Constraints

• T is an integer between 1 and 10^5, inclusive.
• S is a string consisting of A, B, and C with length between 1 and 10^6, inclusive.
• The sum of |S| in each input is at most 10^6.

Sample Input 1

5
CAABCB
B
AAABBC
AABBCC
CABCCBCBAABCBBBAABAABACABBC

Sample Output 1

1
1
0
1
7

This input contains five test cases.

For the first test case, we can perform the operations as follows, for example.

• Choose and delete the third through fifth characters of S= CAABCB. After the operation, S becomes CAB.
• Choose and delete the second through third characters of S= CAB. After the operation, S becomes C.
• No further operations can be performed. S= C has length 1, which is the minimum achievable.

Problem Statement

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

Initially, x=0. For i=1,2,\dots,N in this order, let us choose one of the following two operations to perform.

• Operation 1 : Replace x with x {\rm AND} A_i.
• Operation 2 : Replace x with x {\rm OR} A_i.

Here, operation 2 must be chosen at most K times in total. {\rm AND} denotes the bitwise {\rm AND} operation, and {\rm OR} denotes the bitwise {\rm OR} operation.

Let M be the maximum possible value of x after all operations are finished. Find the number, modulo 998244353, of operation sequences such that the final x equals M.

Here, two operation sequences are distinguished if and only if there exists an integer j (1 \le j \le N) such that the operation chosen at the j-th step differs between them.

T test cases are given; solve each of them.

Constraints

• 1 \le T \le 10^4
• 1 \le K \le N \le 2 \times 10^5
• 0 \le A_i < 2^{60}
• The sum of N in each input is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

5
5 3
3 7 1 2 6
1 1
1
10 8
3 1 4 1 5 9 2 6 5 3
10 5
227966327241983404 430356836747706085 918791034668488208 753980266897555955 1090352658151595591 1077218377572152409 641276315925917062 859382256805178767 103741332934325112 1090530740094421349
33 33
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

3
1
26
1
603979768

This input contains five test cases.

For the first test case, M=7, and the following three operation sequences achieve the final value x=M.

• Perform the operations in the order 1,1,2,2,2. x changes as 0 \to 0 \to 0 \to 1 \to 3 \to 7.
• Perform the operations in the order 1,2,1,2,2. x changes as 0 \to 0 \to 7 \to 1 \to 3 \to 7.
• Perform the operations in the order 2,1,1,2,2. x changes as 0 \to 3 \to 3 \to 1 \to 3 \to 7.

For the fifth test case, note that the answer should be output modulo 998244353.