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
The city where Mocha lives in is called Zhijiang. There are $$$n+1$$$ villages and $$$2n-1$$$ directed roads in this city.

There are two kinds of roads:

- $$$n-1$$$ roads are from village $$$i$$$ to village $$$i+1$$$, for all $$$1\leq i \leq n-1$$$.
- $$$n$$$ roads can be described by a sequence $$$a_1,\ldots,a_n$$$. If $$$a_i=0$$$, the $$$i$$$-th of these roads goes from village $$$i$$$ to village $$$n+1$$$, otherwise it goes from village $$$n+1$$$ to village $$$i$$$, for all $$$1\leq i\leq n$$$.

Mocha plans to go hiking with Taki this weekend. To avoid the trip being boring, they plan to go through every village exactly once. They can start and finish at any villages. Can you help them to draw up a plan?

## Input Format
Each test contains multiple test cases.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — indicates that the number of villages is $$$n+1$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$). If $$$a_i=0$$$, it means that there is a road from village $$$i$$$ to village $$$n+1$$$. If $$$a_i=1$$$, it means that there is a road from village $$$n+1$$$ to village $$$i$$$.

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

## Output Format
For each test case, print a line with $$$n+1$$$ integers, where the $$$i$$$-th number is the $$$i$$$-th village they will go through. If the answer doesn't exist, print $$$-1$$$.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first test case, the city looks like the following graph:

So all possible answers are $$$(1 \to 4 \to 2 \to 3)$$$, $$$(1 \to 2 \to 3 \to 4)$$$.

In the second test case, the city looks like the following graph:

So all possible answers are $$$(4 \to 1 \to 2 \to 3)$$$, $$$(1 \to 2 \to 3 \to 4)$$$, $$$(3 \to 4 \to 1 \to 2)$$$, $$$(2 \to 3 \to 4 \to 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

A forest is an undirected graph without cycles (not necessarily connected).

Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $$$1$$$ to $$$n$$$, and they would like to add edges to their forests such that:

- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge $$$(u, v)$$$ is added to Mocha's forest, then an edge $$$(u, v)$$$ is added to Diana's forest, and vice versa.

Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.

## Input Format
The first line contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 1000$$$, $$$0 \le m_1, m_2 < n$$$) — the number of nodes and the number of initial edges in Mocha's forest and Diana's forest.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Mocha's forest.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Diana's forest.

## Output Format
The first line contains only one integer $$$h$$$, the maximum number of edges Mocha and Diana can add (in each forest).

Each of the next $$$h$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edge you add each time.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first example, we cannot add any edge.

In the second example, the initial forests are as follows.

We can add an edge $$$(2, 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 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
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

A forest is an undirected graph without cycles (not necessarily connected).

Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from $$$1$$$ to $$$n$$$, and they would like to add edges to their forests such that:

- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge $$$(u, v)$$$ is added to Mocha's forest, then an edge $$$(u, v)$$$ is added to Diana's forest, and vice versa.

Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.

## Input Format
The first line contains three integers $$$n$$$, $$$m_1$$$ and $$$m_2$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m_1, m_2 < n$$$) — the number of nodes and the number of initial edges in Mocha's forest and Diana's forest.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Mocha's forest.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edges in Diana's forest.

## Output Format
The first line contains only one integer $$$h$$$, the maximum number of edges Mocha and Diana can add.

Each of the next $$$h$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the edge you add each time.

If there are multiple correct answers, you can print any one of them.

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

## Note
In the first example, we cannot add any edge.

In the second example, the initial forests are as follows.

We can add an edge $$$(2, 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 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
Mocha wants to be an astrologer. There are $$$n$$$ stars which can be seen in Zhijiang, and the brightness of the $$$i$$$-th star is $$$a_i$$$.

Mocha considers that these $$$n$$$ stars form a constellation, and she uses $$$(a_1,a_2,\ldots,a_n)$$$ to show its state. A state is called mathematical if all of the following three conditions are satisfied:

- For all $$$i$$$ ($$$1\le i\le n$$$), $$$a_i$$$ is an integer in the range $$$[l_i, r_i]$$$.
- $$$\sum \limits _{i=1} ^ n a_i \le m$$$.
- $$$\gcd(a_1,a_2,\ldots,a_n)=1$$$.

Here, $$$\gcd(a_1,a_2,\ldots,a_n)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_n$$$.

Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo $$$998\,244\,353$$$.

Two states $$$(a_1,a_2,\ldots,a_n)$$$ and $$$(b_1,b_2,\ldots,b_n)$$$ are considered different if there exists $$$i$$$ ($$$1\le i\le n$$$) such that $$$a_i \ne b_i$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le 10^5$$$) — the number of stars and the upper bound of the sum of the brightness of stars.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the range of the brightness of the $$$i$$$-th star.

## Output Format
Print a single integer — the number of different mathematical states of this constellation, modulo $$$998\,244\,353$$$.

## Examples
```input
2 4
1 3
1 2
```
```output
4
```
-----
```input
5 10
1 10
1 10
1 10
1 10
1 10
```
```output
251
```
-----
```input
5 100
1 94
1 96
1 91
4 96
6 97
```
```output
47464146
```

## Note
In the first example, there are $$$4$$$ different mathematical states of this constellation:

- $$$a_1=1$$$, $$$a_2=1$$$.
- $$$a_1=1$$$, $$$a_2=2$$$.
- $$$a_1=2$$$, $$$a_2=1$$$.
- $$$a_1=3$$$, $$$a_2=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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
CQXYM is counting permutations length of $$$2n$$$.

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

A permutation $$$p$$$(length of $$$2n$$$) will be counted only if the number of $$$i$$$ satisfying $$$p_i<p_{i+1}$$$ is no less than $$$n$$$. For example:

- Permutation $$$[1, 2, 3, 4]$$$ will count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$3$$$ ($$$i = 1$$$, $$$i = 2$$$, $$$i = 3$$$).
- Permutation $$$[3, 2, 1, 4]$$$ won't count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$1$$$ ($$$i = 3$$$).

CQXYM wants you to help him to count the number of such permutations modulo $$$1000000007$$$ ($$$10^9+7$$$).

In addition, modulo operation is to get the remainder. For example:

- $$$7 \mod 3=1$$$, because $$$7 = 3 \cdot 2 + 1$$$,
- $$$15 \mod 4=3$$$, because $$$15 = 4 \cdot 3 + 3$$$.

## Input Format
The input consists of multiple test cases.

The first line contains an integer $$$t (t \geq 1)$$$ — the number of test cases. The description of the test cases follows.

Only one line of each test case contains an integer $$$n(1 \leq n \leq 10^5)$$$.

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

## Output Format
For each test case, print the answer in a single line.

## Examples
```input
4
1
2
9
91234
```
```output
1
12
830455698
890287984
```

## Note
$$$n=1$$$, there is only one permutation that satisfies the condition: $$$[1,2].$$$

In permutation $$$[1,2]$$$, $$$p_1<p_2$$$, and there is one $$$i=1$$$ satisfy the condition. Since $$$1 \geq n$$$, this permutation should be counted. In permutation $$$[2,1]$$$, $$$p_1>p_2$$$. Because $$$0<n$$$, this permutation should not be counted.

$$$n=2$$$, there are $$$12$$$ permutations: $$$[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integer arrays of length $$$N$$$, $$$A1$$$ and $$$A2$$$. You are also given $$$Q$$$ queries of 4 types:

1 k l r x: set $$$Ak_i:=min(Ak_i, x)$$$ for each $$$l \leq i \leq r$$$.

2 k l r x: set $$$Ak_i:=max(Ak_i, x)$$$ for each $$$l \leq i \leq r$$$.

3 k l r x: set $$$Ak_i:=Ak_i+x$$$ for each $$$l \leq i \leq r$$$.

4 l r: find the $$$(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$$$ where $$$F(k)$$$ is the $$$k$$$-th Fibonacci number ($$$F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$$$), and $$$x \% y$$$ denotes the remainder of the division of $$$x$$$ by $$$y$$$.

You should process these queries and answer each query of the fourth type.

## Input Format
The first line contains two integers $$$N$$$ and $$$Q$$$. ($$$1 \leq N, Q \leq 5 \times 10^4$$$)

The second line contains $$$N$$$ integers, array $$$A1_1, A1_2, \dots A1_N$$$. ($$$0 \leq A1_i \leq 10^6$$$)

The third line contains $$$N$$$ integers, array $$$A2_1, A2_2, \dots A2_N$$$. ($$$0 \leq A2_i \leq 10^6$$$)

The next $$$Q$$$ lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. ($$$k \in \{1, 2\}$$$, $$$1 \leq l \leq r \leq N$$$)

For queries of type 1 and 2, $$$0 \leq x \leq 10^9$$$ holds.

For queries of type 3, $$$−10^6 \leq x \leq 10^6$$$ holds.

It is guaranteed that after every query each number in arrays $$$A1$$$ and $$$A2$$$ will be nonnegative.

## Output Format
Print the answer to each query of the fourth type, in separate lines.

## Examples
```input
3 4
1 0 2
2 1 0
4 1 3
3 2 2 2 3
1 1 1 3 0
4 1 3
```
```output
4
4
```
-----
```input
5 4
1 3 5 3 2
4 2 1 3 3
4 1 3
4 2 5
2 1 2 4 6
4 2 4
```
```output
18
26
68
```

## Note
In the first example: The answer for the first query is $$$F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$$$. After the second query, the array $$$A2$$$ changes to $$$[2, 4, 0]$$$. After the third query, the array $$$A1$$$ changes to $$$[0, 0, 0]$$$. The answer for the fourth query is $$$F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$$$.

In the second example: The answer for the first query is $$$F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$$$. The answer for the second query is $$$F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26$$$. After the third query, the array $$$A1$$$ changes to $$$[1, 6, 6, 6, 2]$$$. The answer for the fourth query is $$$F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$$$.

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 an undirected graph of $$$N$$$ nodes and $$$M$$$ edges, $$$E_1, E_2, \dots E_M$$$.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus.

Find the number of pairs $$$(L, R)$$$, ($$$1 \leq L \leq R \leq M$$$) such that, if we delete all the edges except for $$$E_L, E_{L+1}, \dots E_R$$$, the graph is a desert.

## Input Format
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 2.5 \times 10^5$$$, $$$1 \leq M \leq 5 \times 10^5$$$). Each of the next $$$M$$$ lines contains two integers. The $$$i$$$-th line describes the $$$i$$$-th edge. It contains integers $$$U_i$$$ and $$$V_i$$$, the nodes connected by the $$$i$$$-th edge ($$$E_i=(U_i, V_i)$$$). It is guaranteed that $$$1 \leq U_i, V_i \leq N$$$ and $$$U_i \neq V_i$$$.

## Output Format
The output contains one integer number – the answer.

## Examples
```input
5 6
1 2
2 3
3 4
4 5
5 1
2 4
```
```output
20
```
-----
```input
2 3
1 2
1 2
1 2
```
```output
5
```

## Note
In the second example: Graphs for pairs $$$(1, 1)$$$, $$$(2, 2)$$$ and $$$(3, 3)$$$ are deserts because they don't have any cycles. Graphs for pairs $$$(1, 2)$$$ and $$$(2, 3)$$$ have one cycle of length 2 so they are deserts.

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Integers from $$$1$$$ to $$$n$$$ (inclusive) were sorted lexicographically (considering integers as strings). As a result, array $$$a_1, a_2, \dots, a_n$$$ was obtained.

Calculate value of $$$(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$$$.

$$$x \mod y$$$ here means the remainder after division $$$x$$$ by $$$y$$$. This remainder is always non-negative and doesn't exceed $$$y - 1$$$. For example, $$$5 \mod 3 = 2$$$, $$$(-1) \mod 6 = 5$$$.

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$).

## Output Format
Print one integer — the required sum.

## Examples
```input
3
```
```output
0
```
-----
```input
12
```
```output
994733045
```
-----
```input
21
```
```output
978932159
```
-----
```input
1000000000000
```
```output
289817887
```

## Note
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

For example, $$$42$$$ is lexicographically smaller than $$$6$$$, because they differ in the first digit, and $$$4 < 6$$$; $$$42 < 420$$$, because $$$42$$$ is a prefix of $$$420$$$.

Let's denote $$$998244353$$$ as $$$M$$$.

In the first example, array $$$a$$$ is equal to $$$[1, 2, 3]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 2) \mod M = 0 \mod M = 0$$$
- $$$(3 - 3) \mod M = 0 \mod M = 0$$$

As a result, $$$(0 + 0 + 0) \mod 10^9 + 7 = 0$$$

In the second example, array $$$a$$$ is equal to $$$[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 10) \mod M = (-8) \mod M = 998244345$$$
- $$$(3 - 11) \mod M = (-8) \mod M = 998244345$$$
- $$$(4 - 12) \mod M = (-8) \mod M = 998244345$$$
- $$$(5 - 2) \mod M = 3 \mod M = 3$$$
- $$$(6 - 3) \mod M = 3 \mod M = 3$$$
- $$$(7 - 4) \mod M = 3 \mod M = 3$$$
- $$$(8 - 5) \mod M = 3 \mod M = 3$$$
- $$$(9 - 6) \mod M = 3 \mod M = 3$$$
- $$$(10 - 7) \mod M = 3 \mod M = 3$$$
- $$$(11 - 8) \mod M = 3 \mod M = 3$$$
- $$$(12 - 9) \mod M = 3 \mod M = 3$$$

As a result, $$$(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$$$ $$$=$$$ $$$2994733059 \mod 10^9 + 7$$$ $$$=$$$ $$$994733045$$$

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
Shohag has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He can perform the following operation any number of times (possibly, zero):

- Select any positive integer $$$k$$$ (it can be different in different operations).
- Choose any position in the sequence (possibly the beginning or end of the sequence, or in between any two elements) and insert $$$k$$$ into the sequence at this position.
- This way, the sequence $$$a$$$ changes, and the next operation is performed on this changed sequence.

For example, if $$$a=[3,3,4]$$$ and he selects $$$k = 2$$$, then after the operation he can obtain one of the sequences $$$[\underline{2},3,3,4]$$$, $$$[3,\underline{2},3,4]$$$, $$$[3,3,\underline{2},4]$$$, or $$$[3,3,4,\underline{2}]$$$.

Shohag wants this sequence to satisfy the following condition: for each $$$1 \le i \le |a|$$$, $$$a_i \le i$$$. Here, $$$|a|$$$ denotes the size of $$$a$$$.

Help him to find the minimum number of operations that he has to perform to achieve this goal. We can show that under the constraints of the problem it's always possible to achieve this goal in a finite number of operations.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the initial length of the sequence.

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 elements of the sequence.

## Output Format
For each test case, print a single integer  — the minimum number of operations needed to perform to achieve the goal mentioned in the statement.

## Examples
```input
4
3
1 3 4
5
1 2 5 7 4
1
1
3
69 6969 696969
```
```output
1
3
0
696966
```

## Note
In the first test case, we have to perform at least one operation, as $$$a_2=3>2$$$. We can perform the operation $$$[1, 3, 4] \rightarrow [1, \underline{2}, 3, 4]$$$ (the newly inserted element is underlined), now the condition is satisfied.

In the second test case, Shohag can perform the following operations:

$$$[1, 2, 5, 7, 4] \rightarrow [1, 2, \underline{3}, 5, 7, 4] \rightarrow [1, 2, 3, \underline{4}, 5, 7, 4] \rightarrow [1, 2, 3, 4, 5, \underline{3}, 7, 4]$$$.

In the third test case, the sequence already satisfies the condition.

Now solve the problem and return the code.