vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Maksim has $n$ objects and $m$ boxes, each box has size exactly $k$. Objects are numbered from $1$ to $n$ in order from left to right, the size of the $i$-th object is $a_i$.

Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the $i$-th object fits in the current box (the remaining size of the box is greater than or equal to $a_i$), he puts it in the box, and the remaining size of the box decreases by $a_i$. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.

Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.

Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).


-----Input-----

The first line of the input contains three integers $n$, $m$, $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the number of objects, the number of boxes and the size of each box.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the size of the $i$-th object.


-----Output-----

Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.


-----Examples-----
Input
5 2 6
5 2 1 4 2

Output
4

Input
5 1 4
4 2 3 4 1

Output
1

Input
5 3 3
1 2 3 1 1

Output
5



-----Note-----

In the first example Maksim can pack only $4$ objects. Firstly, he tries to pack all the $5$ objects. Distribution of objects will be $[5], [2, 1]$. Maxim cannot pack the next object in the second box and he has no more empty boxes at all. Next he will throw out the first object and the objects distribution will be $[2, 1], [4, 2]$. So the answer is $4$.

In the second example it is obvious that Maksim cannot pack all the objects starting from first, second, third and fourth (in all these cases the distribution of objects is $[4]$), but he can pack the last object ($[1]$).

In the third example Maksim can pack all the objects he has. The distribution will be $[1, 2], [3], [1, 1]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an array $t$ dominated by value $v$ in the next situation.

At first, array $t$ should have at least $2$ elements. Now, let's calculate number of occurrences of each number $num$ in $t$ and define it as $occ(num)$. Then $t$ is dominated (by $v$) if (and only if) $occ(v) > occ(v')$ for any other number $v'$. For example, arrays $[1, 2, 3, 4, 5, 2]$, $[11, 11]$ and $[3, 2, 3, 2, 3]$ are dominated (by $2$, $11$ and $3$ respectevitely) but arrays $[3]$, $[1, 2]$ and $[3, 3, 2, 2, 1]$ are not.

Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.

You are given array $a_1, a_2, \dots, a_n$. Calculate its shortest dominated subarray or say that there are no such subarrays.

The subarray of $a$ is a contiguous part of the array $a$, i. e. the array $a_i, a_{i + 1}, \dots, a_j$ for some $1 \le i \le j \le n$.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 1000$) — the number of test cases. Each test case consists of two lines.

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the corresponding values of the array $a$.

It's guaranteed that the total length of all arrays in one test doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or $-1$ if there are no such subarrays.


-----Example-----
Input
4
1
1
6
1 2 3 4 5 1
9
4 1 2 4 5 4 3 2 1
4
3 3 3 3

Output
-1
6
3
2



-----Note-----

In the first test case, there are no subarrays of length at least $2$, so the answer is $-1$.

In the second test case, the whole array is dominated (by $1$) and it's the only dominated subarray.

In the third test case, the subarray $a_4, a_5, a_6$ is the shortest dominated subarray.

In the fourth test case, all subarrays of length more than one are dominated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.

You will now successively do the following Q operations:

* In the i-th operation, you replace every element whose value is B_{i} with C_{i}.



For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

Constraints

* All values in input are integers.
* 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5}
* B_{i} \neq C_{i}

Input

Input is given from Standard Input in the following format:


N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}


Output

Print Q integers S_{i} to Standard Output in the following format:


S_{1}
S_{2}
\vdots
S_{Q}


Note that S_{i} may not fit into a 32-bit integer.

Examples

Input

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


Output

11
12
16


Input

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


Output

8
4
4


Input

2
1 2
3
1 100
2 100
100 1000


Output

102
200
2000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers a and b, and q queries. The i-th query consists of two numbers l_i and r_i, and the answer to it is the number of integers x such that l_i ≤ x ≤ r_i, and ((x mod a) mod b) ≠ ((x mod b) mod a). Calculate the answer for each query.

Recall that y mod z is the remainder of the division of y by z. For example, 5 mod 3 = 2, 7 mod 8 = 7, 9 mod 4 = 1, 9 mod 9 = 0.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then the test cases follow.

The first line of each test case contains three integers a, b and q (1 ≤ a, b ≤ 200; 1 ≤ q ≤ 500).

Then q lines follow, each containing two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10^{18}) for the corresponding query.

Output

For each test case, print q integers — the answers to the queries of this test case in the order they appear.

Example

Input


2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200


Output


0 0 0 2 4 
0 91 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Winner

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
The winner of the card game popular in Berland "Berlogging" is determined according to the following rules. If at the end of the game there is only one player with the maximum number of points, he is the winner. The situation becomes more difficult if the number of such players is more than one. During each round a player gains or loses a particular number of points. In the course of the game the number of points is registered in the line "name score", where name is a player's name, and score is the number of points gained in this round, which is an integer number. If score is negative, this means that the player has lost in the round. So, if two or more players have the maximum number of points (say, it equals to *m*) at the end of the game, than wins the one of them who scored at least *m* points first. Initially each player has 0 points. It's guaranteed that at the end of the game at least one player has a positive number of points.

Input Specification:
The first line contains an integer number *n* (1<=<=≤<=<=*n*<=<=≤<=<=1000), *n* is the number of rounds played. Then follow *n* lines, containing the information about the rounds in "name score" format in chronological order, where name is a string of lower-case Latin letters with the length from 1 to 32, and score is an integer number between -1000 and 1000, inclusive.

Output Specification:
Print the name of the winner.

Demo Input:
['3\nmike 3\nandrew 5\nmike 2\n', '3\nandrew 3\nandrew 2\nmike 5\n']

Demo Output:
['andrew\n', 'andrew\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Multicolored Cars

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this. Firstly Alice chooses some color *A*, then Bob chooses some color *B* (*A*<=≠<=*B*). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after *i*-th car *cnt**A*(*i*) and *cnt**B*(*i*).
 -  If *cnt**A*(*i*)<=&gt;<=*cnt**B*(*i*) for every *i* then the winner is Alice. -  If *cnt**B*(*i*)<=≥<=*cnt**A*(*i*) for every *i* then the winner is Bob. -  Otherwise it's a draw. 
Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color *A* and Bob now wants to choose such color *B* that he will win the game (draw is not a win). Help him find this color.

If there are multiple solutions, print any of them. If there is no such color then print -1.

Input Specification:
The first line contains two integer numbers *n* and *A* (1<=≤<=*n*<=≤<=105,<=1<=≤<=*A*<=≤<=106) – number of cars and the color chosen by Alice.

The second line contains *n* integer numbers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=106) — colors of the cars that Alice and Bob will encounter in the order of their appearance.

Output Specification:
Output such color *B* (1<=≤<=*B*<=≤<=106) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with (1<=≤<=*B*<=≤<=106).

Demo Input:
['4 1\n2 1 4 2\n', '5 2\n2 2 4 5 3\n', '3 10\n1 2 3\n']

Demo Output:
['2\n', '-1\n', '4\n']

Note:
Let's consider availability of colors in the first example: 
 -  *cnt*<sub class="lower-index">2</sub>(*i*) ≥ *cnt*<sub class="lower-index">1</sub>(*i*) for every *i*, and color 2 can be the answer. -  *cnt*<sub class="lower-index">4</sub>(2) &lt; *cnt*<sub class="lower-index">1</sub>(2), so color 4 isn't the winning one for Bob. -  All the other colors also have *cnt*<sub class="lower-index">*j*</sub>(2) &lt; *cnt*<sub class="lower-index">1</sub>(2), thus they are not available. 
In the third example every color is acceptable except for 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a set of four (4) balls labeled with different numbers: ball_1 (1), ball_2 (2), ball_3 (3) and ball(4) and we have 3 equal boxes for distribute them. The possible combinations of the balls, without having empty boxes, are:

```
 (1)            (2)        (3)(4)     
______        ______       _______ 
    
```

```
 (1)           (2)(4)        (3)
______         ______      ______
  
```

```
(1)(4)           (2)         (3)
______          ______      ______

```

```
  (1)           (2)(3)       (4)
_______         _______     ______

```

```
(1)(3)            (2)        (4)
_______         _______     ______
```

```
(1)(2)            (3)        (4)
_______         _______     ______
```
We have a total of **6** combinations.

Think how many combinations you will have with two boxes instead of three. You will obtain **7** combinations.

Obviously, the four balls in only box will give only one possible combination (the four balls in the unique box). Another particular case is the four balls in four boxes having again one possible combination(Each box having one ball).

What will be the reasonable result for a set of n elements with no boxes?

Think to create a function that may calculate the amount of these combinations of a set of ```n``` elements in ```k``` boxes.

You do no not have to check the inputs type that will be always valid integers.

The code should detect the cases when ```k > n```, returning "It cannot be possible!". 

Features of the random tests:
```
1 <= k <= n <= 800
```
Ruby version will be published soon.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan wants to play a game with you. He picked some string $s$ of length $n$ consisting only of lowercase Latin letters. 

You don't know this string. Ivan has informed you about all its improper prefixes and suffixes (i.e. prefixes and suffixes of lengths from $1$ to $n-1$), but he didn't tell you which strings are prefixes and which are suffixes.

Ivan wants you to guess which of the given $2n-2$ strings are prefixes of the given string and which are suffixes. It may be impossible to guess the string Ivan picked (since multiple strings may give the same set of suffixes and prefixes), but Ivan will accept your answer if there is at least one string that is consistent with it. Let the game begin!


-----Input-----

The first line of the input contains one integer number $n$ ($2 \le n \le 100$) — the length of the guessed string $s$.

The next $2n-2$ lines are contain prefixes and suffixes, one per line. Each of them is the string of length from $1$ to $n-1$ consisting only of lowercase Latin letters. They can be given in arbitrary order.

It is guaranteed that there are exactly $2$ strings of each length from $1$ to $n-1$. It is also guaranteed that these strings are prefixes and suffixes of some existing string of length $n$.


-----Output-----

Print one string of length $2n-2$ — the string consisting only of characters 'P' and 'S'. The number of characters 'P' should be equal to the number of characters 'S'. The $i$-th character of this string should be 'P' if the $i$-th of the input strings is the prefix and 'S' otherwise.

If there are several possible answers, you can print any.


-----Examples-----
Input
5
ba
a
abab
a
aba
baba
ab
aba

Output
SPPSPSPS

Input
3
a
aa
aa
a

Output
PPSS

Input
2
a
c

Output
PS



-----Note-----

The only string which Ivan can guess in the first example is "ababa".

The only string which Ivan can guess in the second example is "aaa". Answers "SPSP", "SSPP" and "PSPS" are also acceptable.

In the third example Ivan can guess the string "ac" or the string "ca". The answer "SP" is also acceptable.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rectangular field of n × m cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (x, y) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (x, y). You should do it for each impassable cell independently.

The answer should be printed as a matrix with n rows and m columns. The j-th symbol of the i-th row should be "." if the cell is empty at the start. Otherwise the j-th symbol of the i-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of n strings having length m and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the field.

Each of the next n lines contains m symbols: "." for empty cells, "*" for impassable cells.


-----Output-----

Print the answer as a matrix as described above. See the examples to precise the format of the output.


-----Examples-----
Input
3 3
*.*
.*.
*.*

Output
3.3
.5.
3.3

Input
4 5
**..*
..***
.*.*.
*.*.*

Output
46..3
..732
.6.4.
5.4.3



-----Note-----

In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You know that Japan is the country with almost the largest 'electronic devices per person' ratio. So you might be quite surprised to find out that the primary school in Japan teaches to count using a Soroban — an abacus developed in Japan. This phenomenon has its reasons, of course, but we are not going to speak about them. Let's have a look at the Soroban's construction. [Image] 

Soroban consists of some number of rods, each rod contains five beads. We will assume that the rods are horizontal lines. One bead on each rod (the leftmost one) is divided from the others by a bar (the reckoning bar). This single bead is called go-dama and four others are ichi-damas. Each rod is responsible for representing a single digit from 0 to 9. We can obtain the value of a digit by following simple algorithm:  Set the value of a digit equal to 0.  If the go-dama is shifted to the right, add 5.  Add the number of ichi-damas shifted to the left. 

Thus, the upper rod on the picture shows digit 0, the middle one shows digit 2 and the lower one shows 7. We will consider the top rod to represent the last decimal digit of a number, so the picture shows number 720.

Write the program that prints the way Soroban shows the given number n.


-----Input-----

The first line contains a single integer n (0 ≤ n < 10^9).


-----Output-----

Print the description of the decimal digits of number n from the last one to the first one (as mentioned on the picture in the statement), one per line. Print the beads as large English letters 'O', rod pieces as character '-' and the reckoning bar as '|'. Print as many rods, as many digits are in the decimal representation of number n without leading zeroes. We can assume that number 0 has no leading zeroes.


-----Examples-----
Input
2

Output
O-|OO-OO

Input
13

Output
O-|OOO-O
O-|O-OOO

Input
720

Output
O-|-OOOO
O-|OO-OO
-O|OO-OO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A binary matrix is called good if every even length square sub-matrix has an odd number of ones. 

Given a binary matrix $a$ consisting of $n$ rows and $m$ columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all. 

All the terms above have their usual meanings — refer to the Notes section for their formal definitions. 


-----Input-----

The first line of input contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 10^6$ and $n\cdot m \leq 10^6$)  — the number of rows and columns in $a$, respectively. 

The following $n$ lines each contain $m$ characters, each of which is one of 0 and 1. If the $j$-th character on the $i$-th line is 1, then $a_{i,j} = 1$. Similarly, if the $j$-th character on the $i$-th line is 0, then $a_{i,j} = 0$.


-----Output-----

Output the minimum number of cells you need to change to make $a$ good, or output $-1$ if it's not possible at all.


-----Examples-----
Input
3 3
101
001
110

Output
2
Input
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011

Output
-1


-----Note-----

In the first case, changing $a_{1,1}$ to $0$ and $a_{2,2}$ to $1$ is enough. 

You can verify that there is no way to make the matrix in the second case good. 

Some definitions —   A binary matrix is one in which every element is either $1$ or $0$.  A sub-matrix is described by $4$ parameters — $r_1$, $r_2$, $c_1$, and $c_2$; here, $1 \leq r_1 \leq r_2 \leq n$ and $1 \leq c_1 \leq c_2 \leq m$.  This sub-matrix contains all elements $a_{i,j}$ that satisfy both $r_1 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$.  A sub-matrix is, further, called an even length square if $r_2-r_1 = c_2-c_1$ and $r_2-r_1+1$ is divisible by $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fafa owns a company that works on huge projects. There are n employees in Fafa's company. Whenever the company has a new project to start working on, Fafa has to divide the tasks of this project among all the employees.

Fafa finds doing this every time is very tiring for him. So, he decided to choose the best l employees in his company as team leaders. Whenever there is a new project, Fafa will divide the tasks among only the team leaders and each team leader will be responsible of some positive number of employees to give them the tasks. To make this process fair for the team leaders, each one of them should be responsible for the same number of employees. Moreover, every employee, who is not a team leader, has to be under the responsibility of exactly one team leader, and no team leader is responsible for another team leader.

Given the number of employees n, find in how many ways Fafa could choose the number of team leaders l in such a way that it is possible to divide employees between them evenly.


-----Input-----

The input consists of a single line containing a positive integer n (2 ≤ n ≤ 10^5) — the number of employees in Fafa's company.


-----Output-----

Print a single integer representing the answer to the problem.


-----Examples-----
Input
2

Output
1

Input
10

Output
3



-----Note-----

In the second sample Fafa has 3 ways:  choose only 1 employee as a team leader with 9 employees under his responsibility.  choose 2 employees as team leaders with 4 employees under the responsibility of each of them.  choose 5 employees as team leaders with 1 employee under the responsibility of each of them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $\mbox{Q}$ queries. Each query consists of a single number $N$. You can perform any of the $2$ operations on $N$ in each move:

1: If we take 2 integers $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ where $N=a\times b$ $(a\neq1$, $b\neq1)$, then we can change $N=max(a,b)$

2: Decrease the value of $N$ by $1$. 

Determine the minimum number of moves required to reduce the value of $N$ to $0$.

Input Format

The first line contains the integer $Q$. 

The next $Q$ lines each contain an integer, $N$.  

Constraints

$1\leq Q\leq10^3$ 

$0\leq N\leq10^6$  

Output Format

Output $Q$ lines. Each line containing the minimum number of moves required to reduce the value of $N$ to $0$.

Sample Input
2
3
4

Sample Output
3
3

Explanation

For test case 1, We only have one option that gives the minimum number of moves. 

Follow $3$ -> $2$ -> $\mbox{1}$ -> $0$. Hence, $3$ moves.

For the case 2, we can either go $\begin{array}{c}4\end{array}$ -> $3$ -> $2$ -> $1$ -> $0$ or $\begin{array}{c}4\end{array}$ -> $2$ -> $1$ -> $0$. The 2nd option is more optimal. Hence, $3$ moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.