Problem Statement

Takahashi set task goals for N days.

He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.

Find the number of days when he completed more tasks than his goal.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i, B_i \leq 100
• All input values are integers.

Sample Input 1

4
2 8
5 5
5 4
6 7

Sample Output 1

2

Takahashi completed more tasks than his goal on the 1st and 4th days.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

6
1 6
2 5
3 4
4 3
5 2
6 1

Sample Output 3

3

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

There are N dominoes numbered from 1 to N. The size of domino i is S_i.
Consider arranging some dominoes in a line from left to right and then toppling them. When domino i falls to the right, if the size of the domino placed immediately to the right of domino i is at most 2 S_i, then that domino also falls to the right.

You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions:

• The leftmost domino is domino 1.
• The rightmost domino is domino N.
• When only domino 1 is toppled to the right, domino N eventually falls to the right as well.

Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged?

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

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_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

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

Sample Output 1

4
-1
3

For the 1st test case, arranging the dominoes from left to right in the order domino 1, domino 3, domino 2, domino 4 satisfies the conditions in the problem statement. Specifically, for the 3rd condition, when only domino 1 is toppled to the right, the dominoes fall in the following order:

• Domino 3 is placed to the right of domino 1. Since the size of domino 3, S_3 = 2, is not greater than S_1 \times 2 = 1 \times 2 = 2, domino 3 also falls to the right.
• Domino 2 is placed to the right of domino 3. Since the size of domino 2, S_2 = 3, is not greater than S_3 \times 2 = 2 \times 2 = 4, domino 2 also falls to the right.
• Domino 4 is placed to the right of domino 2. Since the size of domino 4, S_4 = 5, is not greater than S_2 \times 2 = 3 \times 2 = 6, domino 4 also falls to the right.

It is impossible to achieve the conditions in the problem statement by arranging 3 or fewer dominoes, so the answer is 4.

Problem Statement

There is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and the i-th edge is an undirected edge connecting vertices A_i and B_i.

You can repeat the following two operations in any order and any number of times:

• Add one undirected edge to G
• Remove one undirected edge from G

Find the minimum number of operations to make G a simple undirected graph where all vertices have degree 2.

Constraints

• 3 \leq N \leq 8
• 0 \leq M \leq \frac{N(N-1)}{2}
• The graph G given in the input is a simple undirected graph.
• All input values are integers.

Sample Input 1

5 4
1 2
1 5
2 4
4 5

Sample Output 1

3

For example, the following three operations make G a simple undirected graph where all vertices have degree 2.

• Add an edge connecting vertices 2 and 3.
• Remove the edge connecting vertices 2 and 4.
• Add an edge connecting vertices 3 and 4.

Sample Input 2

3 0

Sample Output 2

3

Sample Input 3

6 8
1 4
1 5
2 3
2 6
3 4
3 6
4 5
4 6

Sample Output 3

2

Sample Input 4

8 21
1 4
5 7
8 4
3 4
2 5
8 1
5 1
2 8
2 1
2 4
3 1
6 7
5 8
2 7
6 8
5 4
3 8
7 3
7 8
5 3
7 4

Sample Output 4

13

Problem Statement

For a positive integer n, define A_n as the least common multiple of 1, 2, \dots, n.
You are given positive integers L and R. How many distinct integers are contained in the sequence (A_L, A_{L+1}, \dots, A_R)?

Constraints

• 1 \leq L \leq R \leq 10^{14}
• R - L \leq 10^7
• L and R are integers.

Sample Input 1

4 12

Sample Output 1

6

Listing A_4 through A_{12}:

• A_4 = 12
• A_5 = 60
• A_6 = 60
• A_7 = 420
• A_8 = 840
• A_9 = 2520
• A_{10} = 2520
• A_{11} = 27720
• A_{12} = 27720

Thus, (A_4, A_5, \dots, A_{12}) contains six distinct integers.

Sample Input 2

123456789 123456789

Sample Output 2

1

Sample Input 3

99999990000000 100000000000000

Sample Output 3

310458

Problem Statement

In Takahashi's chest of drawers, there are socks of N colors, with A_i socks of color i.

Initially, Takahashi has one sock of color C outside the chest of drawers, separate from these socks, and repeats the following operation until the termination condition is met:

• Uniformly randomly choose and draw 1 sock from the chest of drawers. Then, if the two socks he has outside the chest of drawers are the same color, terminate the operation. Otherwise, choose one of the socks and put it back in the chest of drawers. He always chooses the sock to put back so as to minimize the expected number of future sock draws.

Find the expected number, modulo 998244353, of sock draws until the operation terminates.

Constraints

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

Sample Input 1

3 2
3 1 2

Sample Output 1

249561092

The expected number of sock draws is \frac{15}{4}.

Sample Input 2

8 4
4 1 6 2 5 1 7 3

Sample Output 2

393623786

Problem Statement

You are given a simple undirected graph G with N vertices and M edges, where vertices are numbered from 1 to N. The i-th edge connects vertices u_i and v_i.
A spanning subgraph G' of G that satisfies the following condition is called a good graph:

• For all integers i satisfying 1 \leq i \leq N, the following condition holds:
  • Let d_i be the degree of vertex i in G'. Then, d_i \leq A_i and d_i \bmod 2 = A_i \bmod 2 hold.

Determine whether a good graph exists. If it exists, output the minimum number of edges among all possible good graphs.

Constraints

• 1 \leq N \leq 150
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• 1 \leq A_i \leq 150
• 1 \leq \sum_{i=1}^N A_i \leq 150
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2
1 3
2 3

Sample Output 1

1

The spanning subgraph whose edge set consists of only the 2nd edge is a good graph.

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

5 6
3 1 4 3 1
1 2
1 3
1 4
2 3
3 4
3 5

Sample Output 3

3