yl-9/probench huggingface dataset:
# Satyam and Counting

## Problem Description

Satyam is given $ n $ distinct points on the 2D coordinate plane. It is guaranteed that $ 0 \leq y_i \leq 1 $ for all given points $ (x_i, y_i) $ . How many different nondegenerate right triangles $ ^{\text{∗}} $ can be formed from choosing three different points as its vertices?

Two triangles $ a $ and $ b $ are different if there is a point $ v $ such that $ v $ is a vertex of $ a $ but not a vertex of $ b $ .

 $ ^{\text{∗}} $ A nondegenerate right triangle has positive area and an interior $ 90^{\circ} $ angle.

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — the number of points.

The following $ n $ lines contain two integers $ x_i $ and $ y_i $ ( $ 0 \leq x_i \leq n $ , $ 0 \leq y_i \leq 1 $ ) — the $ i $ 'th point that Satyam can choose from. It is guaranteed that all $ (x_i, y_i) $ are pairwise distinct.

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

## Output Format

Output an integer for each test case, the number of distinct nondegenerate right triangles that can be formed from choosing three points.

## Sample #1

### Sample Input #1

```
3
5
1 0
1 1
3 0
5 0
2 1
3
0 0
1 0
3 0
9
1 0
2 0
3 0
4 0
5 0
2 1
7 1
8 1
9 1
```

### Sample Output #1

```
4
0
8
```

## Hint

The four triangles in question for the first test case:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2009D/34af5d1e01dabd5b071d413da74fdbeb85cca657.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: geometry, math
Difficulty: 1400
# The Legend of Freya the Frog

## Problem Description

Freya the Frog is traveling on the 2D coordinate plane. She is currently at point $ (0,0) $ and wants to go to point $ (x,y) $ . In one move, she chooses an integer $ d $ such that $ 0 \leq d \leq k $ and jumps $ d $ spots forward in the direction she is facing.

Initially, she is facing the positive $ x $ direction. After every move, she will alternate between facing the positive $ x $ direction and the positive $ y $ direction (i.e., she will face the positive $ y $ direction on her second move, the positive $ x $ direction on her third move, and so on).

What is the minimum amount of moves she must perform to land on point $ (x,y) $ ?

## Input Format

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

Each test case contains three integers $ x $ , $ y $ , and $ k $ ( $ 0 \leq x, y \leq 10^9, 1 \leq k \leq 10^9 $ ).

## Output Format

For each test case, output the number of jumps Freya needs to make on a new line.

## Sample #1

### Sample Input #1

```
3
9 11 3
0 10 8
1000000 100000 10
```

### Sample Output #1

```
8
4
199999
```

## Hint

In the first sample, one optimal set of moves is if Freya jumps in the following way: ( $ 0,0 $ ) $ \rightarrow $ ( $ 2,0 $ ) $ \rightarrow $ ( $ 2,2 $ ) $ \rightarrow $ ( $ 3,2 $ ) $ \rightarrow $ ( $ 3,5 $ ) $ \rightarrow $ ( $ 6,5 $ ) $ \rightarrow $ ( $ 6,8 $ ) $ \rightarrow $ ( $ 9,8 $ ) $ \rightarrow $ ( $ 9,11 $ ). This takes 8 jumps.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 1100
# osu!mania

## Problem Description

You are playing your favorite rhythm game, osu!mania. The layout of your beatmap consists of $ n $ rows and $ 4 $ columns. Because notes at the bottom are closer, you will process the bottommost row first and the topmost row last. Each row will contain exactly one note, represented as a '#'.

For each note $ 1, 2, \dots, n $ , in the order of processing, output the column in which the note appears.

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

For each test case, the first line contains $ n $ ( $ 1 \leq n \leq 500 $ ) — the number of rows of the beatmap.

The following $ n $ lines contain $ 4 $ characters. The $ i $ -th line represents the $ i $ -th row of the beatmap from the top. It is guaranteed that the characters are either '.' or '#', and exactly one of the characters is '#'.

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

## Output Format

For each test case, output $ n $ integers on a new line, the column that the $ i $ -th note appears in for all $ i $ from $ 1 $ to $ n $ .

## Sample #1

### Sample Input #1

```
3
4
#...
.#..
..#.
...#
2
.#..
.#..
1
...#
```

### Sample Output #1

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

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, implementation
Difficulty: 800
# Minimize!

## Problem Description

You are given two integers $ a $ and $ b $ ( $ a \leq b $ ). Over all possible integer values of $ c $ ( $ a \leq c \leq b $ ), find the minimum value of $ (c - a) + (b - c) $ .

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 55 $ ) — the number of test cases.

Each test case contains two integers $ a $ and $ b $ ( $ 1 \leq a \leq b \leq 10 $ ).

## Output Format

For each test case, output the minimum possible value of $ (c - a) + (b - c) $ on a new line.

## Sample #1

### Sample Input #1

```
3
1 2
3 10
5 5
```

### Sample Output #1

```
1
7
0
```

## Hint

In the first test case, you can choose $ c = 1 $ and obtain an answer of $ (1 - 1) + (2 - 1) = 1 $ . It can be shown this is the minimum value possible.

In the second test case, you can choose $ c = 6 $ and obtain an answer of $ (6 - 3) + (10 - 6) = 7 $ . It can be shown this is the minimum value possible.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, math
Difficulty: 800
# Sakurako's Test

## Problem Description

Sakurako will soon take a test. The test can be described as an array of integers $ n $ and a task on it:

Given an integer $ x $ , Sakurako can perform the following operation any number of times:

- Choose an integer $ i $ ( $ 1\le i\le n $ ) such that $ a_i\ge x $ ;
- Change the value of $ a_i $ to $ a_i-x $ .

Using this operation any number of times, she must find the minimum possible median $ ^{\text{∗}} $ of the array $ a $ .

Sakurako knows the array but does not know the integer $ x $ . Someone let it slip that one of the $ q $ values of $ x $ will be in the next test, so Sakurako is asking you what the answer is for each such $ x $ .

 $ ^{\text{∗}} $ The median of an array of length $ n $ is the element that stands in the middle of the sorted array (at the $ \frac{n+2}{2} $ -th position for even $ n $ , and at the $ \frac{n+1}{2} $ -th for odd)

## Input Format

The first line contains one integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ q $ ( $ 1\le n,q\le 10^5 $ ) — the number of elements in the array and the number of queries.

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

The following $ q $ lines each contain one integer $ x $ ( $ 1\le x\le n $ ).

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10^5 $ . The same guarantee applies to the sum of $ q $ across all test cases.

## Output Format

For each test case, output $ q $ integers — the answer for each query.

## Sample #1

### Sample Input #1

```
2
5 5
1 2 3 4 5
1
2
3
4
5
6 3
1 2 6 4 1 3
2
1
5
```

### Sample Output #1

```
0 1 1 1 2 
1 0 2
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, brute force, greedy, math, number theory
Difficulty: 2100
# Sakurako's Task

## Problem Description

Sakurako has prepared a task for you:

She gives you an array of $ n $ integers and allows you to choose $ i $ and $ j $ such that $ i \neq j $ and $ a_i \ge a_j $ , and then assign $ a_i = a_i - a_j $ or $ a_i = a_i + a_j $ . You can perform this operation any number of times for any $ i $ and $ j $ , as long as they satisfy the conditions.

Sakurako asks you what is the maximum possible value of $ mex_k $ $ ^{\text{∗}} $ of the array after any number of operations.

 $ ^{\text{∗}} $ $ mex_k $ is the $ k $ -th non-negative integer that is absent in the array. For example, $ mex_1(\{1,2,3 \})=0 $ , since $ 0 $ is the first element that is not in the array, and $ mex_2(\{0,2,4 \})=3 $ , since $ 3 $ is the second element that is not in the array.

## Input Format

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

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1\le n\le 2\cdot 10^5,1\le k\le 10^9 $ ) — the number of elements in the array and the value $ k $ for $ mex_k $ .

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.

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

## Output Format

For each test case, output the maximum $ mex_k $ that can be achieved through the operations.

## Sample #1

### Sample Input #1

```
6
1 3
3
2 10
1 1
3 1
1 2 3
3 2
1 2 4
4 5
2 2 2 16
4 5
2 2 2 3
```

### Sample Output #1

```
2
11
3
4
8
8
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, greedy, math, number theory
Difficulty: 1800
# Sakurako's Box

## Problem Description

Sakurako has a box with $ n $ balls. Each ball has it's value. She wants to bet with her friend that if the friend randomly picks two balls from the box (it could be two distinct balls, but they may have the same value), the product of their values will be the same as the number that Sakurako guessed.

Since Sakurako has a PhD in probability, she knows that the best number to pick is [the expected value](http://tiny.cc/matozh_en), but she forgot how to calculate it. Help Sakurako and find the expected value of the product of two elements from the array.

It can be shown that the expected value has the form $ \frac{P}{Q} $ , where $ P $ and $ Q $ are non-negative integers, and $ Q \ne 0 $ . Report the value of $ P \cdot Q^{-1}(\bmod 10^9+7) $ .

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 2\le n\le 2\cdot 10^5 $ ) — the number of elements in the array.

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

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

## Output Format

For each test case, output the value of $ P \cdot Q^{-1}(\bmod 10^9+7) $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
7
6
500000012
```

## Hint

For the first test, Sakurako's friend can pick these pairs of balls: $ (a_1,a_2) $ , $ (a_1,a_3) $ , $ (a_2,a_3) $ . Their products equal to $ 3\cdot 2=6 $ , $ 3\cdot 3=9 $ , $ 3\cdot 2=6 $ respectively, so the expected value is $ \frac{6+9+6}{3}=7 $ .

For the second test, Sakurako's friend can pick these pairs of balls: $ (a_1,a_2) $ , $ (a_1,a_3) $ , $ (a_1,a_4) $ , $ (a_2,a_3) $ , $ (a_2,a_4) $ , $ (a_3,a_4) $ . Their products equal to $ 2\cdot 2=4 $ , $ 2\cdot 2=4 $ , $ 2\cdot 4=8 $ , $ 2\cdot 2=4 $ , $ 2\cdot 4=8 $ , $ 2\cdot 4=8 $ respectively, so the expected value is $ \frac{4+4+8+4+8+8}{6}=\frac{36}{6}=6 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, math, number theory
Difficulty: 1400
# Alternating String

## Problem Description

Sakurako really loves alternating strings. She calls a string $ s $ of lowercase Latin letters an alternating string if characters in the even positions are the same, if characters in the odd positions are the same, and the length of the string is even.

For example, the strings 'abab' and 'gg' are alternating, while the strings 'aba' and 'ggwp' are not.

As a good friend, you decided to gift such a string, but you couldn't find one. Luckily, you can perform two types of operations on the string:

1. Choose an index $ i $ and delete the $ i $ -th character from the string, which will reduce the length of the string by $ 1 $ . This type of operation can be performed no more than $ 1 $ time;
2. Choose an index $ i $ and replace $ s_i $ with any other letter.

Since you are in a hurry, you need to determine the minimum number of operations required to make the string an alternating one.

## Input Format

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

The first line of each test case contains a single number $ n $ ( $ 1 \le n\le 2\cdot 10^5 $ ) — the length of the string.

The second line of each test case contains a string $ s $ , consisting of lowercase Latin letters.

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

## Output Format

For each test case, output a single integer — the minimum number of operations required to turn the string $ s $ into an alternating one.

## Sample #1

### Sample Input #1

```
10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb
```

### Sample Output #1

```
1
0
1
1
2
6
2
3
1
1
```

## Hint

For the string ababa, you can delete the first character to get baba, which is an alternating string.

For the string acdada, you can change the first two characters to get dadada, which is an alternating string.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, data structures, dp, greedy, implementation, strings
Difficulty: 1500
# Sakurako's Hobby

## Problem Description

For a certain permutation $ p $ $ ^{\text{∗}} $ Sakurako calls an integer $ j $ reachable from an integer $ i $ if it is possible to make $ i $ equal to $ j $ by assigning $ i=p_i $ a certain number of times.

If $ p=[3,5,6,1,2,4] $ , then, for example, $ 4 $ is reachable from $ 1 $ , because: $ i=1 $ $ \rightarrow $ $ i=p_1=3 $ $ \rightarrow $ $ i=p_3=6 $ $ \rightarrow $ $ i=p_6=4 $ . Now $ i=4 $ , so $ 4 $ is reachable from $ 1 $ .

Each number in the permutation is colored either black or white.

Sakurako defines the function $ F(i) $ as the number of black integers that are reachable from $ i $ .

Sakurako is interested in $ F(i) $ for each $ 1\le i\le n $ , but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this.

 $ ^{\text{∗}} $ A permutation of length $ n $ 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 (the number $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ , but the array contains $ 4 $ ).

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the number of elements in the array.

The second line of each test case contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1\le p_i\le n $ ) — the elements of the permutation.

The third line of each test case contains a string $ s $ of length $ n $ , consisting of '0' and '1'. If $ s_i=0 $ , then the number $ p_i $ is colored black; if $ s_i=1 $ , then the number $ p_i $ is colored white.

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

## Output Format

For each test case, output $ n $ integers $ F(1), F(2), \dots, F(n) $ .

## Sample #1

### Sample Input #1

```
5
1
1
0
5
1 2 4 5 3
10101
5
5 4 1 3 2
10011
6
3 5 6 1 2 4
010000
6
1 2 3 4 5 6
100110
```

### Sample Output #1

```
1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dp, dsu, graphs, math
Difficulty: 1100
# Longest Good Array

## Problem Description

Today, Sakurako was studying arrays. An array $ a $ of length $ n $ is considered good if and only if:

- the array $ a $ is increasing, meaning $ a_{i - 1} < a_i $ for all $ 2 \le i \le n $ ;
- the differences between adjacent elements are increasing, meaning $ a_i - a_{i-1} < a_{i+1} - a_i $ for all $ 2 \le i < n $ .

Sakurako has come up with boundaries $ l $ and $ r $ and wants to construct a good array of maximum length, where $ l \le a_i \le r $ for all $ a_i $ .

Help Sakurako find the maximum length of a good array for the given $ l $ and $ r $ .

## Input Format

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

The only line of each test case contains two integers $ l $ and $ r $ ( $ 1\le l\le r\le 10^9 $ ).

## Output Format

For each test case, output a single integer — the length of the longest good array Sakurako can form given $ l $ and $ r $ .

## Sample #1

### Sample Input #1

```
5
1 2
1 5
2 2
10 20
1 1000000000
```

### Sample Output #1

```
2
3
1
5
44721
```

## Hint

For $ l=1 $ and $ r=5 $ , one possible array could be $ (1,2,5) $ . It can be proven that an array of length $ 4 $ does not exist for the given $ l $ and $ r $ .

For $ l=2 $ and $ r=2 $ , the only possible array is $ (2) $ .

For $ l=10 $ and $ r=20 $ , the only possible array is $ (10,11,13,16,20) $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, brute force, math
Difficulty: 800
# Square or Not

## Problem Description

A beautiful binary matrix is a matrix that has ones on its edges and zeros inside.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2008B/82ff9b44b2f58835e7545bc3f71e9003425cf95f.png) Examples of four beautiful binary matrices.Today, Sakurako was playing with a beautiful binary matrix of size $ r \times c $ and created a binary string $ s $ by writing down all the rows of the matrix, starting from the first and ending with the $ r $ -th. More formally, the element from the matrix in the $ i $ -th row and $ j $ -th column corresponds to the $ ((i-1)*c+j) $ -th element of the string.

You need to check whether the beautiful matrix from which the string $ s $ was obtained could be squared. In other words, you need to check whether the string $ s $ could have been build from a square beautiful binary matrix (i.e., one where $ r=c $ ).

## Input Format

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

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

The second line of each test case contains the string $ s $ of length $ n $ . The string is always the result of writing out the strings of a beautiful matrix.

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

## Output Format

Print "Yes", if the original matrix could have been square, and "No" otherwise.

## Sample #1

### Sample Input #1

```
5
2
11
4
1111
9
111101111
9
111111111
12
111110011111
```

### Sample Output #1

```
No
Yes
Yes
No
No
```

## Hint

For the second test case, string 1111 can be obtained from the matrix:

  $ 1 $  $ 1 $  $ 1 $  $ 1 $ For the third test case, string 111101111 can be obtained from the matrix:

  $ 1 $  $ 1 $  $ 1 $  $ 1 $  $ 0 $  $ 1 $  $ 1 $  $ 1 $  $ 1 $ There is no square matrix in the fourth case, such that the string can be obtained from it.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, math, strings
Difficulty: 800
# Sakurako's Exam

## Problem Description

Today, Sakurako has a math exam. The teacher gave the array, consisting of $ a $ ones and $ b $ twos.

In an array, Sakurako must place either a '+' or a '-' in front of each element so that the sum of all elements in the array equals $ 0 $ .

Sakurako is not sure if it is possible to solve this problem, so determine whether there is a way to assign signs such that the sum of all elements in the array equals $ 0 $ .

## Input Format

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

The only line of each test case contains two integers $ a $ and $ b $ ( $ 0\le a,b<10 $ ) — the number of '1's and the number of '2's in the array.

## Output Format

For each test case, output "Yes" if you can make the sum of the entire array equal to $ 0 $ , and "No" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Sample #1

### Sample Input #1

```
5
0 1
0 3
2 0
2 3
3 1
```

### Sample Output #1

```
NO
NO
YES
YES
NO
```

## Hint

1. $ a=0 $ , $ b=1 $ : This means the array is $ [2] $ — it is impossible to add the signs '+' or '-' to get $ 0 $ as a result;
2. $ a=0 $ , $ b=3 $ : This means the array is $ [2, 2, 2] $ — it is impossible to add the signs '+' or '-' to get $ 0 $ as a result;
3. $ a=2 $ , $ b=0 $ : This means the array is $ [1, 1] $ — it is possible to add the signs '+' or '-' to get $ 0 $ as a result ( $ +1-1=0 $ );
4. $ a=2 $ , $ b=3 $ : This means the array is $ [1, 1, 2, 2, 2] $ — it is possible to add the signs '+' or '-' to get $ 0 $ as a result ( $ +1+1-2-2+2=0 $ );

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, greedy, math
Difficulty: 800
# Dora and C++

## Problem Description

Dora has just learned the programming language C++!

However, she has completely misunderstood the meaning of C++. She considers it as two kinds of adding operations on the array $ c $ with $ n $ elements. Dora has two integers $ a $ and $ b $ . In one operation, she can choose one of the following things to do.

- Choose an integer $ i $ such that $ 1 \leq i \leq n $ , and increase $ c_i $ by $ a $ .
- Choose an integer $ i $ such that $ 1 \leq i \leq n $ , and increase $ c_i $ by $ b $ .

Note that $ a $ and $ b $ are constants, and they can be the same.

Let's define a range of array $ d $ as $ \max(d_i) - \min(d_i) $ . For instance, the range of the array $ [1, 2, 3, 4] $ is $ 4 - 1 = 3 $ , the range of the array $ [5, 2, 8, 2, 2, 1] $ is $ 8 - 1 = 7 $ , and the range of the array $ [3, 3, 3] $ is $ 3 - 3 = 0 $ .

After any number of operations (possibly, $ 0 $ ), Dora calculates the range of the new array. You need to help Dora minimize this value, but since Dora loves exploring all by herself, you only need to tell her the minimized value.

## Input Format

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $ n $ , $ a $ , and $ b $ ( $ 1 \leq n \leq 10^5 $ , $ 1 \leq a, b \leq 10^9 $ ) — the length of the array $ c $ and the constant values, respectively.

The second line of each test case contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \leq c_i \leq 10^9 $ ) — the initial elements of the array $ c $ .

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

## Output Format

For each test case, output a single integer — the minimum possible range of the array after any number of operations.

## Sample #1

### Sample Input #1

```
10
4 5 5
1 3 4 4
4 2 3
1 3 4 6
4 7 7
1 1 2 6
3 15 9
1 9 5
3 18 12
1 4 5
7 27 36
33 13 23 12 35 24 41
10 6 9
15 5 6 9 8 2 12 15 3 8
2 1 1000000000
1 1000000000
6 336718728 709848696
552806726 474775724 15129785 371139304 178408298 13106071
6 335734893 671469786
138885253 70095920 456876775 9345665 214704906 375508929
```

### Sample Output #1

```
3
0
3
2
3
5
1
0
17
205359241
```

## Hint

In the first test case, we can increase $ c_1 = 1 $ by $ a = 5 $ . The array $ c $ will become $ [6, 3, 4, 4] $ , and the range is $ 3 $ . Note that there is more than one way to reach the answer.

In the second test case, we can increase $ c_1 = 1 $ by $ a = 2 $ and then increase $ c_1 = 3 $ by $ b = 3 $ . Also, we can increase $ c_2 = 3 $ by $ b = 3 $ and increase $ c_3 = 4 $ by $ a = 2 $ . The array $ c $ will become $ [6, 6, 6, 6] $ , and the range is $ 0 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: math, number theory
Difficulty: 1500