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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
In Japan, the number $$$4$$$ reads like death, so Bob decided to build a live sequence. Living sequence $$$a$$$ contains all natural numbers that do not contain the digit $$$4$$$. $$$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$$$.

For example, the number $$$1235$$$ is part of the sequence $$$a$$$, but the numbers $$$4321$$$, $$$443$$$ are not part of the sequence $$$a$$$.

Bob realized that he does not know how to quickly search for a particular number by the position $$$k$$$ in the sequence, so he asks for your help.

For example, if Bob wants to find the number at position $$$k = 4$$$ (indexing from $$$1$$$), you need to answer $$$a_k = 5$$$.

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

In the only line of each test case, there is a single integer $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — the position Bob is interested in.

## Output Format
For each test case, print on a separate line the number $$$a_k$$$ in indexing with $$$1$$$.

## Examples
```input
7
3
5
22
10
100
12345
827264634912
```
```output
3
6
25
11
121
18937
2932285320890
```

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
Vlad found a flowerbed with graphs in his yard and decided to take one for himself. Later he found out that in addition to the usual graphs, $$$k$$$-flowers also grew on that flowerbed. A graph is called a $$$k$$$-flower if it consists of a simple cycle of length $$$k$$$, through each vertex of which passes its own simple cycle of length $$$k$$$ and these cycles do not intersect at the vertices. For example, $$$3$$$-flower looks like this:

Note that $$$1$$$-flower and $$$2$$$-flower do not exist, since at least $$$3$$$ vertices are needed to form a cycle.

Vlad really liked the structure of the $$$k$$$-flowers and now he wants to find out if he was lucky to take one of them from the flowerbed.

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

The descriptions of the cases follow. An empty string is written before each case.

The first line of each case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(2 \cdot 10^5, \frac{n \cdot (n-1)}{2})$$$) — the number of vertices and edges in the graph, respectively.

The next $$$m$$$ lines contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — numbers of vertices connected by an edge. It is guaranteed that the graph does not contain multiple edges and self-loops.

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

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if Vlad's graph is a $$$k$$$-flower for some $$$k$$$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

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

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: 256.0 MB

# Problem
This is an easy version of the problem, it differs from the hard one only by constraints on $$$n$$$ and $$$k$$$.

Vlad found a row of $$$n$$$ tiles and the integer $$$k$$$. The tiles are indexed from left to right and the $$$i$$$-th tile has the color $$$c_i$$$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $$$p$$$. Let's call the path $$$p$$$ of length $$$m$$$ nice if:

- $$$p$$$ can be divided into blocks of length exactly $$$k$$$, that is, $$$m$$$ is divisible by $$$k$$$;
- $$$c_{p_1} = c_{p_2} = \ldots = c_{p_k}$$$;
- $$$c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$$$;
- $$$\ldots$$$
- $$$c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$$$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — tile colors.

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

## Output Format
Print $$$t$$$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $$$10^9 + 7$$$.

## Examples
```input
5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5
```
```output
1
4
165
3
1
```

## Note
In the first sample, it is impossible to make a nice path with a length greater than $$$0$$$.

In the second sample, we are interested in the following paths:

- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$
- $$$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$

In the third example, any path of length $$$8$$$ is nice.

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 a positive integer $$$n$$$. Please find an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

A perfect array $$$a_1, a_2, \ldots, a_n$$$ satisfies the following criteria:

- $$$1 \le a_i \le 1000$$$ for all $$$1 \le i \le n$$$.
- $$$a_i$$$ is divisible by $$$i$$$ for all $$$1 \le i \le n$$$.
- $$$a_1 + a_2 + \ldots + a_n$$$ is divisible by $$$n$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The only line of each test case contains a single positive integer $$$n$$$ ($$$1 \le n \le 200$$$) — the length of the array $$$a$$$.

## Output Format
For each test case, output an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

We can show that an answer always exists. If there are multiple solutions, print any.

## Examples
```input
7
1
2
3
4
5
6
7
```
```output
1
2 4
1 2 3
2 8 6 4
3 4 9 4 5
1 10 18 8 5 36
3 6 21 24 10 6 14
```

## Note
In the third test case:

- $$$a_1 = 1$$$ is divisible by $$$1$$$.
- $$$a_2 = 2$$$ is divisible by $$$2$$$.
- $$$a_3 = 3$$$ is divisible by $$$3$$$.
- $$$a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$$$ is divisible by $$$3$$$.

In the fifth test case:

- $$$a_1 = 3$$$ is divisible by $$$1$$$.
- $$$a_2 = 4$$$ is divisible by $$$2$$$.
- $$$a_3 = 9$$$ is divisible by $$$3$$$.
- $$$a_4 = 4$$$ is divisible by $$$4$$$.
- $$$a_5 = 5$$$ is divisible by $$$5$$$.
- $$$a_1 + a_2 + a_3 + a_4 + a_5 = 3 + 4 + 9 + 4 + 5 = 25$$$ is divisible by $$$5$$$.

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 an unsorted permutation $$$p_1, p_2, \ldots, p_n$$$. To sort the permutation, you choose a constant $$$k$$$ ($$$k \ge 1$$$) and do some operations on the permutation. In one operation, you can choose two integers $$$i$$$, $$$j$$$ ($$$1 \le j < i \le n$$$) such that $$$i - j = k$$$, then swap $$$p_i$$$ and $$$p_j$$$.

What is the maximum value of $$$k$$$ that you can choose to sort the given permutation?

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 unsorted permutation $$$p$$$ is a permutation such that there is at least one position $$$i$$$ that satisfies $$$p_i \ne i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^{5}$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$. It is guaranteed that the given numbers form a permutation of length $$$n$$$ and the given permutation is unsorted.

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

## Output Format
For each test case, output the maximum value of $$$k$$$ that you can choose to sort the given permutation.

We can show that an answer always exists.

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

## Note
In the first test case, the maximum value of $$$k$$$ you can choose is $$$1$$$. The operations used to sort the permutation are:

- Swap $$$p_2$$$ and $$$p_1$$$ ($$$2 - 1 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 3, 2]$$$
- Swap $$$p_2$$$ and $$$p_3$$$ ($$$3 - 2 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3]$$$

In the second test case, the maximum value of $$$k$$$ you can choose is $$$2$$$. The operations used to sort the permutation are:

- Swap $$$p_3$$$ and $$$p_1$$$ ($$$3 - 1 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 4, 3, 2]$$$
- Swap $$$p_4$$$ and $$$p_2$$$ ($$$4 - 2 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3, 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
Given an array $$$a$$$ of length $$$n$$$, which elements are equal to $$$-1$$$ and $$$1$$$. Let's call the array $$$a$$$ good if the following conditions are held at the same time:

- $$$a_1 + a_2 + \ldots + a_n \ge 0$$$;
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1$$$.

In one operation, you can select an arbitrary element of the array $$$a_i$$$ and change its value to the opposite. In other words, if $$$a_i = -1$$$, you can assign the value to $$$a_i := 1$$$, and if $$$a_i = 1$$$, then assign the value to $$$a_i := -1$$$.

Determine the minimum number of operations you need to perform to make the array $$$a$$$ good. It can be shown that this is always possible.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = \pm 1$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations that need to be done to make the $$$a$$$ array good.

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

## Note
In the first test case, we can assign the value $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$$$. Thus, we performed $$$1$$$ operation.

In the second test case, we can assign $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$1$$$ operation.

In the third test case, $$$a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$$$. Thus, all conditions are already satisfied and no operations are needed.

In the fourth test case, we can assign the values $$$a_1 := 1, a_2 := 1, a_3 := 1$$$. Then $$$a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$3$$$ operations.

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
Zinaida Viktorovna has $$$n$$$ students in her history class. The homework for today included $$$m$$$ topics, but the students had little time to prepare, so $$$i$$$-th student learned only topics from $$$l_i$$$ to $$$r_i$$$ inclusive.

At the beginning of the lesson, each student holds their hand at $$$0$$$. The teacher wants to ask some topics. It goes like this:

- The teacher asks the topic $$$k$$$.
- If the student has learned topic $$$k$$$, then he raises his hand by $$$1$$$, otherwise he lower it by $$$1$$$.

Each topic Zinaida Viktorovna can ask no more than one time.

Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.

Note that the student's hand can go below $$$0$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^9$$$) — the number of students and the number of topics, respectively.

Each of the next $$$n$$$ lines of each test case contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the endpoints of the segment of topics that $$$i$$$-th student has learned.

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

## Output Format
For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

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

## Note
In the first test case, Zinaida Viktorovna can ask the topics $$$5, 6, 7, 8$$$. Then the hand of the $$$2$$$-nd student will be at the height of $$$4$$$, and the hand of the $$$4$$$-th will be at the height of $$$-2$$$, that is, the difference will be equal to $$$6$$$.

In the second test case, you can ask about the topics $$$1$$$ and $$$3$$$. Then the hand of the $$$1$$$-st student will be at the height of $$$2$$$ and the hand of the $$$3$$$-rd student will be at the height of $$$-2$$$. So the difference will be $$$4$$$.

In the third test case, the difference between the highest and lowest hand will be $$$0$$$ for any set of topics asked.

In the fifth test case, you can ask all topics. Then the difference between the heights of the $$$1$$$-st and $$$3$$$-rd students' hands will be $$$12$$$.

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: 512.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$. A positive integer $$$x$$$ is called good if it is impossible to find a subsegment$$$^{\dagger}$$$ of the array such that the least common multiple of all its elements is equal to $$$x$$$.

You need to find the smallest good integer.

A subsegment$$$^{\dagger}$$$ of the array $$$a$$$ is a set of elements $$$a_l, a_{l + 1}, \ldots, a_r$$$ for some $$$1 \le l \le r \le n$$$. We will denote such subsegment as $$$[l, r]$$$.

## Input Format
Each test consists of multiple test cases. The first line of each test case contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

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

## Output Format
For each test case, output a single integer — the smallest good integer.

## Examples
```input
6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9
```
```output
4
7
1
1
16
13
```

## Note
In the first test case, $$$4$$$ is a good integer, and it is the smallest one, since the integers $$$1,2,3$$$ appear in the array, which means that there are subsegments of the array of length $$$1$$$ with least common multiples of $$$1,2,3$$$. However, it is impossible to find a subsegment of the array with a least common multiple equal to $$$4$$$.

In the second test case, $$$7$$$ is a good integer. The integers $$$1,2,3,4,5$$$ appear explicitly in the array, and the integer $$$6$$$ is the least common multiple of the subsegments $$$[2, 3]$$$ and $$$[1, 3]$$$.

In the third test case, $$$1$$$ is a good integer, since the least common multiples for the integer in the subsegments $$$[1, 1], [1, 2], [2, 2]$$$ are $$$2,6,3$$$, 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 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
Alphen has an array of positive integers $$$a$$$ of length $$$n$$$.

Alphen can perform the following operation:

- For all $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_i$$$ with $$$\max(0, a_i - 1)$$$.

Alphen will perform the above operation until $$$a$$$ is sorted, that is $$$a$$$ satisfies $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$. How many operations will Alphen perform? Under the constraints of the problem, it can be proven that Alphen will perform a finite number of operations.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, output a single integer — the number of operations that Alphen will perform.

## Examples
```input
7
3
1 2 3
5
2 1 2 1 2
4
3 1 5 4
2
7 7
5
4 1 3 2 5
5
2 3 1 4 5
3
1000000000 1 2
```
```output
0
2
5
0
4
3
1000000000
```

## Note
In the first test case, we have $$$a=[1,2,3]$$$. Since $$$a$$$ is already sorted, Alphen will not need to perform any operations. So, the answer is $$$0$$$.

In the second test case, we have $$$a=[2,1,2,1,2]$$$. Since $$$a$$$ is not initially sorted, Alphen will perform one operation to make $$$a=[1,0,1,0,1]$$$. After performing one operation, $$$a$$$ is still not sorted, so Alphen will perform another operation to make $$$a=[0,0,0,0,0]$$$. Since $$$a$$$ is sorted, Alphen will not perform any other operations. Since Alphen has performed two operations in total, the answer is $$$2$$$.

Now solve the problem and return the code.