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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a large electronic screen which can display up to $$$998244353$$$ decimal digits. The digits are displayed in the same way as on different electronic alarm clocks: each place for a digit consists of $$$7$$$ segments which can be turned on and off to compose different digits. The following picture describes how you can display all $$$10$$$ decimal digits:

As you can see, different digits may require different number of segments to be turned on. For example, if you want to display $$$1$$$, you have to turn on $$$2$$$ segments of the screen, and if you want to display $$$8$$$, all $$$7$$$ segments of some place to display a digit should be turned on.

You want to display a really large integer on the screen. Unfortunately, the screen is bugged: no more than $$$n$$$ segments can be turned on simultaneously. So now you wonder what is the greatest integer that can be displayed by turning on no more than $$$n$$$ segments.

Your program should be able to process $$$t$$$ different test cases.

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

Then the test cases follow, each of them is represented by a separate line containing one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the maximum number of segments that can be turned on in the corresponding testcase.

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

## Output Format
For each test case, print the greatest integer that can be displayed by turning on no more than $$$n$$$ segments of the screen. Note that the answer may not fit in the standard $$$32$$$-bit or $$$64$$$-bit integral data type.

## Examples
```input
2
3
4
```
```output
7
11
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given string $$$s$$$ of length $$$n$$$ consisting of 0-s and 1-s. You build an infinite string $$$t$$$ as a concatenation of an infinite number of strings $$$s$$$, or $$$t = ssss \dots$$$ For example, if $$$s =$$$ 10010, then $$$t =$$$ 100101001010010...

Calculate the number of prefixes of $$$t$$$ with balance equal to $$$x$$$. The balance of some string $$$q$$$ is equal to $$$cnt_{0, q} - cnt_{1, q}$$$, where $$$cnt_{0, q}$$$ is the number of occurrences of 0 in $$$q$$$, and $$$cnt_{1, q}$$$ is the number of occurrences of 1 in $$$q$$$. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

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

Next $$$2T$$$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$-10^9 \le x \le 10^9$$$) — the length of string $$$s$$$ and the desired balance, respectively.

The second line contains the binary string $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{\text{0}, \text{1}\}$$$).

It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$10^5$$$.

## Output Format
Print $$$T$$$ integers — one per test case. For each test case print the number of prefixes or $$$-1$$$ if there is an infinite number of such prefixes.

## Examples
```input
4
6 10
010010
5 3
10101
1 0
0
2 0
01
```
```output
3
0
1
-1
```

## Note
In the first test case, there are 3 good prefixes of $$$t$$$: with length $$$28$$$, $$$30$$$ and $$$32$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. Also you have a string $$$z$$$ which is initially empty. You want string $$$z$$$ to be equal to string $$$t$$$. You can perform the following operation to achieve this: append any subsequence of $$$s$$$ at the end of string $$$z$$$. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if $$$z = ac$$$, $$$s = abcde$$$, you may turn $$$z$$$ into following strings in one operation:

1. $$$z = acace$$$ (if we choose subsequence $$$ace$$$);
2. $$$z = acbcd$$$ (if we choose subsequence $$$bcd$$$);
3. $$$z = acbce$$$ (if we choose subsequence $$$bce$$$).

Note that after this operation string $$$s$$$ doesn't change.

Calculate the minimum number of such operations to turn string $$$z$$$ into string $$$t$$$.

## Input Format
The first line contains the integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

The first line of each testcase contains one string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase Latin letters.

The second line of each testcase contains one string $$$t$$$ ($$$1 \le |t| \le 10^5$$$) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings $$$s$$$ and $$$t$$$ in the input does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print one integer — the minimum number of operations to turn string $$$z$$$ into string $$$t$$$. If it's impossible print $$$-1$$$.

## Examples
```input
3
aabce
ace
abacaba
aax
ty
yyt
```
```output
1
-1
3
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$a$$$ and $$$m$$$. Calculate the number of integers $$$x$$$ such that $$$0 \le x < m$$$ and $$$\gcd(a, m) = \gcd(a + x, m)$$$.

Note: $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.

## Input Format
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 50$$$) — the number of test cases.

Next $$$T$$$ lines contain test cases — one per line. Each line contains two integers $$$a$$$ and $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$).

## Output Format
Print $$$T$$$ integers — one per test case. For each test case print the number of appropriate $$$x$$$-s.

## Examples
```input
3
4 9
5 10
42 9999999967
```
```output
6
1
9999999966
```

## Note
In the first test case appropriate $$$x$$$-s are $$$[0, 1, 3, 4, 6, 7]$$$.

In the second test case the only appropriate $$$x$$$ is $$$0$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p_1, p_2, \dots , p_n$$$ (an array where each integer from $$$1$$$ to $$$n$$$ appears exactly once). The weight of the $$$i$$$-th element of this permutation is $$$a_i$$$.

At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements $$$p_1, p_2, \dots , p_k$$$, the second — $$$p_{k+1}, p_{k+2}, \dots , p_n$$$, where $$$1 \le k < n$$$.

After that, you may move elements between sets. The operation you are allowed to do is to choose some element of the first set and move it to the second set, or vice versa (move from the second set to the first). You have to pay $$$a_i$$$ dollars to move the element $$$p_i$$$.

Your goal is to make it so that each element of the first set is less than each element of the second set. Note that if one of the sets is empty, this condition is met.

For example, if $$$p = [3, 1, 2]$$$ and $$$a = [7, 1, 4]$$$, then the optimal strategy is: separate $$$p$$$ into two parts $$$[3, 1]$$$ and $$$[2]$$$ and then move the $$$2$$$-element into first set (it costs $$$4$$$). And if $$$p = [3, 5, 1, 6, 2, 4]$$$, $$$a = [9, 1, 9, 9, 1, 9]$$$, then the optimal strategy is: separate $$$p$$$ into two parts $$$[3, 5, 1]$$$ and $$$[6, 2, 4]$$$, and then move the $$$2$$$-element into first set (it costs $$$1$$$), and $$$5$$$-element into second set (it also costs $$$1$$$).

Calculate the minimum number of dollars you have to spend.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots , p_n$$$ ($$$1 \le p_i \le n$$$). It's guaranteed that this sequence contains each element from $$$1$$$ to $$$n$$$ exactly once.

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

## Output Format
Print one integer — the minimum number of dollars you have to spend.

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

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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
An online contest will soon be held on ForceCoders, a large competitive programming platform. The authors have prepared $$$n$$$ problems; and since the platform is very popular, $$$998244351$$$ coder from all over the world is going to solve them.

For each problem, the authors estimated the number of people who would solve it: for the $$$i$$$-th problem, the number of accepted solutions will be between $$$l_i$$$ and $$$r_i$$$, inclusive.

The creator of ForceCoders uses different criteria to determine if the contest is good or bad. One of these criteria is the number of inversions in the problem order. An inversion is a pair of problems $$$(x, y)$$$ such that $$$x$$$ is located earlier in the contest ($$$x < y$$$), but the number of accepted solutions for $$$y$$$ is strictly greater.

Obviously, both the creator of ForceCoders and the authors of the contest want the contest to be good. Now they want to calculate the probability that there will be no inversions in the problem order, assuming that for each problem $$$i$$$, any integral number of accepted solutions for it (between $$$l_i$$$ and $$$r_i$$$) is equally probable, and all these numbers are independent.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of problems in the contest.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 998244351$$$) — the minimum and maximum number of accepted solutions for the $$$i$$$-th problem, respectively.

## Output Format
The probability that there will be no inversions in the contest can be expressed as an irreducible fraction $$$\frac{x}{y}$$$, where $$$y$$$ is coprime with $$$998244353$$$. Print one integer — the value of $$$xy^{-1}$$$, taken modulo $$$998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$yy^{-1} \equiv 1$$$ $$$(mod$$$ $$$998244353)$$$.

## Examples
```input
3
1 2
1 2
1 2
```
```output
499122177
```
-----
```input
2
42 1337
13 420
```
```output
578894053
```
-----
```input
2
1 1
0 0
```
```output
1
```
-----
```input
2
1 1
1 1
```
```output
1
```

## Note
The real answer in the first test is $$$\frac{1}{2}$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 64.0 MB

# Problem
Little Petya likes numbers a lot. He found that number 123 in base 16 consists of two digits: the first is 7 and the second is 11. So the sum of digits of 123 in base 16 is equal to 18.

Now he wonders what is an average value of sum of digits of the number A written in all bases from 2 to A - 1.

Note that all computations should be done in base 10. You should find the result as an irreducible fraction, written in base 10.

## Input Format
Input contains one integer number A (3 ≤ A ≤ 1000).

## Output Format
Output should contain required average value in format «X/Y», where X is the numerator and Y is the denominator.

## Examples
```input
5
```
```output
7/3
```
-----
```input
3
```
```output
2/1
```

## Note
In the first sample number 5 written in all bases from 2 to 4 looks so: 101, 12, 11. Sums of digits are 2, 3 and 2, respectively.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 64.0 MB

# Problem
Little Petya likes to play very much. And most of all he likes to play the following game:

He is given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.

The sequence a is called non-decreasing if a1 ≤ a2 ≤ ... ≤ aN holds, where N is the length of the sequence.

## Input Format
The first line of the input contains single integer N (1 ≤ N ≤ 5000) — the length of the initial sequence. The following N lines contain one integer each — elements of the sequence. These numbers do not exceed 109 by absolute value.

## Output Format
Output one integer — minimum number of steps required to achieve the goal.

## Examples
```input
5
3 2 -1 2 11
```
```output
4
```
-----
```input
5
2 1 1 1 1
```
```output
1
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 64.0 MB

# Problem
Little Petya likes to draw. He drew N red and M blue points on the plane in such a way that no three points lie on the same line. Now he wonders what is the number of distinct triangles with vertices in red points which do not contain any blue point inside.

## Input Format
The first line contains two non-negative integer numbers N and M (0 ≤ N ≤ 500, 0 ≤ M ≤ 500) — the number of red and blue points respectively. The following N lines contain two integer numbers each — coordinates of red points. The following M lines contain two integer numbers each — coordinates of blue points. All coordinates do not exceed 109 by absolute value.

## Output Format
Output one integer — the number of distinct triangles with vertices in red points which do not contain any blue point inside.

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

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Guy-Manuel and Thomas have an array $$$a$$$ of $$$n$$$ integers [$$$a_1, a_2, \dots, a_n$$$]. In one step they can add $$$1$$$ to any element of the array. Formally, in one step they can choose any integer index $$$i$$$ ($$$1 \le i \le n$$$) and do $$$a_i := a_i + 1$$$.

If either the sum or the product of all elements in the array is equal to zero, Guy-Manuel and Thomas do not mind to do this operation one more time.

What is the minimum number of steps they need to do to make both the sum and the product of all elements in the array different from zero? Formally, find the minimum number of steps to make $$$a_1 + a_2 +$$$ $$$\dots$$$ $$$+ a_n \ne 0$$$ and $$$a_1 \cdot a_2 \cdot$$$ $$$\dots$$$ $$$\cdot a_n \ne 0$$$.

## Input Format
Each test contains multiple test cases.

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — elements of the array .

## Output Format
For each test case, output the minimum number of steps required to make both sum and product of all elements in the array different from zero.

## Examples
```input
4
3
2 -1 -1
4
-1 0 0 1
2
-1 2
3
0 -2 1
```
```output
1
2
0
2
```

## Note
In the first test case, the sum is $$$0$$$. If we add $$$1$$$ to the first element, the array will be $$$[3,-1,-1]$$$, the sum will be equal to $$$1$$$ and the product will be equal to $$$3$$$.

In the second test case, both product and sum are $$$0$$$. If we add $$$1$$$ to the second and the third element, the array will be $$$[-1,1,1,1]$$$, the sum will be equal to $$$2$$$ and the product will be equal to $$$-1$$$. It can be shown that fewer steps can't be enough.

In the third test case, both sum and product are non-zero, we don't need to do anything.

In the fourth test case, after adding $$$1$$$ twice to the first element the array will be $$$[2,-2,1]$$$, the sum will be $$$1$$$ and the product will be $$$-4$$$.

Now solve the problem and return the code.