apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarpus has n friends in Tarasov city. Polycarpus knows phone numbers of all his friends: they are strings s1, s2, ..., sn. All these strings consist only of digits and have the same length.

Once Polycarpus needed to figure out Tarasov city phone code. He assumed that the phone code of the city is the longest common prefix of all phone numbers of his friends. In other words, it is the longest string c which is a prefix (the beginning) of each si for all i (1 ≤ i ≤ n). Help Polycarpus determine the length of the city phone code.

## Input Format
The first line of the input contains an integer n (2 ≤ n ≤ 3·104) — the number of Polycarpus's friends. The following n lines contain strings s1, s2, ..., sn — the phone numbers of Polycarpus's friends. It is guaranteed that all strings consist only of digits and have the same length from 1 to 20, inclusive. It is also guaranteed that all strings are different.

## Output Format
Print the number of digits in the city phone code.

## Examples
```input
4
00209
00219
00999
00909
```
```output
2
```
-----
```input
2
1
2
```
```output
0
```
-----
```input
3
77012345678999999999
77012345678901234567
77012345678998765432
```
```output
12
```

## Note
A prefix of string t is a string that is obtained by deleting zero or more digits from the end of string t. For example, string "00209" has 6 prefixes: "" (an empty prefix), "0", "00", "002", "0020", "00209".

In the first sample the city phone code is string "00".

In the second sample the city phone code is an empty string.

In the third sample the city phone code is string "770123456789".

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way: $$r_{i} = (a \cdot r_{i-1} + b) \mod m$$ (for i ≥ 1). Here a, b, m are constants, fixed for the given realization of the pseudorandom numbers generator, r0 is the so-called randseed (this value can be set from the program using functions like RandSeed(r) or srand(n)), and $$\bmod$$ denotes the operation of taking the remainder of division.

For example, if a = 2, b = 6, m = 12, r0 = 11, the generated sequence will be: 4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....

Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.

Your task is to find the period of a sequence defined by the given values of a, b, m and r0. Formally, you have to find such minimum positive integer t, for which exists such positive integer k, that for any i ≥ k: ri = ri + t.

## Input Format
The single line of the input contains four integers a, b, m and r0 (1 ≤ m ≤ 105, 0 ≤ a, b ≤ 1000, 0 ≤ r0 < m), separated by single spaces.

## Output Format
Print a single integer — the period of the sequence.

## Examples
```input
2 6 12 11
```
```output
2
```
-----
```input
2 3 5 1
```
```output
4
```
-----
```input
3 6 81 9
```
```output
1
```

## Note
The first sample is described above.

In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...

In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One day, Vogons wanted to build a new hyperspace highway through a distant system with $$$n$$$ planets. The $$$i$$$-th planet is on the orbit $$$a_i$$$, there could be multiple planets on the same orbit. It's a pity that all the planets are on the way and need to be destructed.

Vogons have two machines to do that.

- The first machine in one operation can destroy any planet at cost of $$$1$$$ Triganic Pu.
- The second machine in one operation can destroy all planets on a single orbit in this system at the cost of $$$c$$$ Triganic Pus.

Vogons can use each machine as many times as they want.

Vogons are very greedy, so they want to destroy all planets with minimum amount of money spent. Can you help them to know the minimum cost of this project?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow.

Each test case consists of two lines.

The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n, c \le 100$$$) — the number of planets and the cost of the second machine usage.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the orbit of the $$$i$$$-th planet.

## Output Format
For each test case print a single integer — the minimum cost of destroying all planets.

## Examples
```input
4
10 1
2 1 4 5 2 4 5 5 1 2
5 2
3 2 1 2 2
2 2
1 1
2 2
1 2
```
```output
4
4
2
2
```
-----
```input
1
1 100
1
```
```output
1
```

## Note
In the first test case, the cost of using both machines is the same, so you can always use the second one and destroy all planets in orbit $$$1$$$, all planets in orbit $$$2$$$, all planets in orbit $$$4$$$, all planets in orbit $$$5$$$.

In the second test case, it is advantageous to use the second machine for $$$2$$$ Triganic Pus to destroy all the planets in orbit $$$2$$$, then destroy the remaining two planets using the first machine.

In the third test case, you can use the first machine twice or the second machine once.

In the fourth test case, it is advantageous to use the first machine twice.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a string $$$s$$$ consisting of digits from $$$0$$$ to $$$9$$$ inclusive. You can perform the following operation any (possibly zero) number of times:

- You can choose a position $$$i$$$ and delete a digit $$$d$$$ on the $$$i$$$-th position. Then insert the digit $$$\min{(d + 1, 9)}$$$ on any position (at the beginning, at the end or in between any two adjacent digits).

What is the lexicographically smallest string you can get by performing these operations?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a smaller digit than the corresponding digit in $$$b$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.

Each test case consists of a single line that contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — the string consisting of digits. Please note that $$$s$$$ is just a string consisting of digits, so leading zeros are allowed.

It is guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print a single string — the minimum string that is possible to obtain.

## Examples
```input
4
04829
9
01
314752277691991
```
```output
02599
9
01
111334567888999
```

## Note
In the first test case:

- Delete $$$8$$$ and insert $$$9$$$ at the end of the notation. The resulting notation is $$$04299$$$.
- Delete $$$4$$$ and insert $$$5$$$ in the $$$3$$$-rd position of the notation. The resulting notation is $$$02599$$$.

Nothing needs to be done in the second and third test cases.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have two strings $$$s_1$$$ and $$$s_2$$$ of length $$$n$$$, consisting of lowercase English letters. You can perform the following operation any (possibly zero) number of times:

- Choose a positive integer $$$1 \leq k \leq n$$$.
- Swap the prefix of the string $$$s_1$$$ and the suffix of the string $$$s_2$$$ of length $$$k$$$.

Is it possible to make these two strings equal by doing described operations?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the strings $$$s_1$$$ and $$$s_2$$$.

The second line contains the string $$$s_1$$$ of length $$$n$$$, consisting of lowercase English letters.

The third line contains the string $$$s_2$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print "YES" if it is possible to make the strings equal, and "NO" otherwise.

## Examples
```input
7
3
cbc
aba
5
abcaa
cbabb
5
abcaa
cbabz
1
a
a
1
a
b
6
abadaa
adaaba
8
abcabdaa
adabcaba
```
```output
YES
YES
NO
YES
NO
NO
YES
```

## Note
In the first test case:

- Initially $$$s_1 = \mathtt{cbc}$$$, $$$s_2 = \mathtt{aba}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{abc}$$$, $$$s_2 = \mathtt{abc}$$$.

In the second test case:

- Initially $$$s_1 = \mathtt{abcaa}$$$, $$$s_2 = \mathtt{cbabb}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{bbcaa}$$$, $$$s_2 = \mathtt{cbaab}$$$.
- Operation with $$$k = 3$$$, after the operation $$$s_1 = \mathtt{aabaa}$$$, $$$s_2 = \mathtt{cbbbc}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{cabaa}$$$, $$$s_2 = \mathtt{cbbba}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{babaa}$$$, $$$s_2 = \mathtt{cbbca}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{aabaa}$$$, $$$s_2 = \mathtt{cbbcb}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{cbbaa}$$$, $$$s_2 = \mathtt{cbbaa}$$$.

In the third test case, it's impossible to make strings equal.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

Find the number of pairs of indices $$$(l, r)$$$, where $$$1 \le l \le r \le n$$$, that pass the check. The check is performed in the following manner:

1. The minimum and maximum numbers are found among $$$a_l, a_{l+1}, \ldots, a_r$$$.
2. The check is passed if the maximum number is divisible by the minimum number.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then the test cases follow.

Each test case consists of two lines.

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of pairs of indices that pass the check.

## Examples
```input
6
1
1
2
2 4
2
2 3
4
2 4 7 14
7
16 5 18 7 7 12 14
6
16 14 2 6 16 2
```
```output
1
3
2
7
10
19
```

## Note
Below $$$x \mid y$$$ denotes that $$$y$$$ is divisible by $$$x$$$.

In the first test case, there is one pair $$$(1, 1)$$$, the maximum for this pair is $$$1$$$, the minimum is also $$$1$$$, $$$1 \mid 1$$$, so the check is passed, and the answer is $$$1$$$.

In the second test case, there are $$$3$$$ segments:

- $$$(1, 1)$$$: the maximum is $$$2$$$, the minimum is $$$2$$$, $$$2 \mid 2$$$, so the check is passed.
- $$$(1, 2)$$$: the maximum is $$$4$$$, the minimum is $$$2$$$, $$$2 \mid 4$$$, so the check is passed.
- $$$(2, 2)$$$: the maximum is $$$4$$$, the minimum is $$$4$$$, $$$4 \mid 4$$$, so the check is passed.

In the third test case, there are $$$3$$$ segments:

- $$$(1, 1)$$$: the maximum is $$$2$$$, the minimum is $$$2$$$, $$$2 \mid 2$$$, so the check is passed.
- $$$(1, 2)$$$: the maximum is $$$3$$$, the minimum is $$$2$$$, $$$3$$$ isn't divisible by $$$2$$$, so the check is failed.
- $$$(2, 2)$$$: the maximum is $$$3$$$, the minimum is $$$3$$$, $$$3 \mid 3$$$, so the check is passed.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of length $$$n$$$ and a positive integer $$$k$$$. Consider a permutation $$$q$$$ of length $$$n$$$ such that for any integers $$$i$$$ and $$$j$$$, where $$$1 \le i < j \le n$$$, we have $$$$$$p_{q_i} \le p_{q_j} + k.$$$$$$

Find the minimum possible number of inversions in a permutation $$$q$$$.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

An inversion in a permutation $$$a$$$ is a pair of indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) such that $$$i < j$$$, but $$$a_i > a_j$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5000$$$, $$$1 \le k \le 8$$$).

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

## Output Format
Print the minimum possible number of inversions in the permutation $$$q$$$.

## Examples
```input
1 1
1
```
```output
0
```
-----
```input
3 1
2 3 1
```
```output
1
```
-----
```input
5 2
5 4 3 2 1
```
```output
6
```
-----
```input
10 3
5 8 6 10 2 7 4 1 9 3
```
```output
18
```

## Note
In the first example, the only permutation is $$$q = [1]$$$ ($$$0$$$ inversions). Then $$$p_{q_1} = 1$$$.

In the second example, the only permutation with $$$1$$$ inversion is $$$q = [1, 3, 2]$$$. Then $$$p_{q_1} = 2$$$, $$$p_{q_2} = 1$$$, $$$p_{q_3} = 3$$$.

In the third example, one of the possible permutations with $$$6$$$ inversions is $$$q = [3, 4, 5, 1, 2]$$$. Then $$$p_{q_1} = 3$$$, $$$p_{q_2} = 2$$$, $$$p_{q_3} = 1$$$, $$$p_{q_4} = 5$$$, $$$p_{q_5} = 4$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ sticks with positive integral length $$$a_1, a_2, \ldots, a_n$$$.

You can perform the following operation any number of times (possibly zero):

- choose one stick, then either increase or decrease its length by $$$1$$$. After each operation, all sticks should have positive lengths.

What is the minimum number of operations that you have to perform such that it is possible to select three of the $$$n$$$ sticks and use them without breaking to form an equilateral triangle?

An equilateral triangle is a triangle where all of its three sides have the same length.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 300$$$) — the number of sticks.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the lengths of the sticks.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300$$$.

## Output Format
For each test case, print one integer on a single line — the minimum number of operations to be made.

## Examples
```input
4
3
1 2 3
4
7 3 7 3
5
3 4 2 1 1
8
3 1 4 1 5 9 2 6
```
```output
2
4
1
1
```

## Note
In the first test case, you can increase the length of the first stick by $$$1$$$, then decrease the length of the third stick by $$$1$$$. In total, you perform $$$2$$$ operations, such that the three sticks form an equilateral triangle of side length $$$2$$$.

In the fourth test case, you can decrease the length of the seventh stick by $$$1$$$. An equilateral triangle of side length $$$1$$$ can be selected and formed by the second, fourth, and seventh sticks.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a set $$$S$$$, which contains the first $$$n$$$ positive integers: $$$1, 2, \ldots, n$$$.

You can perform the following operation on $$$S$$$ any number of times (possibly zero):

- Choose a positive integer $$$k$$$ where $$$1 \le k \le n$$$, such that there exists a multiple of $$$k$$$ in $$$S$$$. Then, delete the smallest multiple of $$$k$$$ from $$$S$$$. This operation requires a cost of $$$k$$$.

You are given a set $$$T$$$, which is a subset of $$$S$$$. Find the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$. We can show that such a transformation is always possible.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. The description of the test cases follows.

The first line contains a single positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line of each test case contains a binary string of length $$$n$$$, describing the set $$$T$$$. The $$$i$$$-th character of the string is '1' if and only if $$$i$$$ is an element of $$$T$$$, and '0' otherwise.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output one non-negative integer — the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$.

## Examples
```input
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100
```
```output
0
11
4
4
17
60
```

## Note
In the first test case, we shall not perform any operations as $$$S$$$ is already equal to $$$T$$$, which is the set $$$\{1, 2, 3, 4, 5, 6\}$$$.

In the second test case, initially, $$$S = \{1, 2, 3, 4, 5, 6, 7\}$$$, and $$$T = \{1, 2, 4, 7\}$$$. We shall perform the following operations:

1. Choose $$$k=3$$$, then delete $$$3$$$ from $$$S$$$.
2. Choose $$$k=3$$$, then delete $$$6$$$ from $$$S$$$.
3. Choose $$$k=5$$$, then delete $$$5$$$ from $$$S$$$.

The total cost is $$$3+3+5 = 11$$$. It can be shown that this is the smallest cost possible.

In the third test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{\}$$$ (empty set). We shall perform $$$4$$$ operations of $$$k=1$$$ to delete $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$.

In the fourth test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{3\}$$$. We shall perform two operations with $$$k=1$$$ to delete $$$1$$$ and $$$2$$$, then perform one operation with $$$k=2$$$ to delete $$$4$$$.

Now solve the problem and return the code.