yl-9/probench huggingface dataset:
# Diverse Game

## Problem Description

Petr, watching Sergey's stream, came up with a matrix $ a $ , consisting of $ n $ rows and $ m $ columns (the number in the $ i $ -th row and $ j $ -th column is denoted as $ a_{i, j} $ ), which contains all integers from $ 1 $ to $ n \cdot m $ . But he didn't like the arrangement of the numbers, and now he wants to come up with a new matrix $ b $ , consisting of $ n $ rows and $ m $ columns, which will also contain all integers from $ 1 $ to $ n \cdot m $ , such that for any $ 1 \leq i \leq n, 1 \leq j \leq m $ it holds that $ a_{i, j} \ne b_{i, j} $ .

You are given the matrix $ a $ , construct any matrix $ b $ that meets Petr's requirements, or determine that it is impossible.

Hurry up! Otherwise, he will donate all his money to the stream in search of an answer to his question.

## Input Format

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

The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 10 $ ) — the number of rows and columns of matrix $ a $ .

The next $ n $ lines contain $ m $ integers each, describing matrix $ a $ . The $ i $ -th of these lines contains the elements of matrix $ a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} $ .

It is guaranteed that all numbers in matrix $ a $ are distinct and $ 1 \leq a_{i, j} \leq n \cdot m $ .

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

## Output Format

For each test case, output $ n \cdot m $ integers — any suitable matrix $ b $ , or $ -1 $ if such a matrix does not exist.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
-1
1 
2 
4 5 3 1 2 
6 7 8 5 
2 3 4 1 
8 3 9 
7 5 6 
2 1 4
```

## Hint

In the first test case, there is only one element in the matrix, so matrix $ b $ is the only matrix and it does not fit.

In the second test case $ a_{1, 1} = 2 \neq 1 = b_{1, 1} $ , $ a_{2, 1} = 1 \neq 2 = b_{2, 1} $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, implementation
Difficulty: 800
# Dyn-scripted Robot (Hard Version)

## Problem Description

This is the hard version of the problem. The only difference is that in this version $ k \le 10^{12} $ . You can make hacks only if both versions of the problem are solved.

Given a $ w \times h $ rectangle on the $ Oxy $ plane, with points $ (0, 0) $ at the bottom-left and $ (w, h) $ at the top-right of the rectangle.

You also have a robot initially at point $ (0, 0) $ and a script $ s $ of $ n $ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.

The robot can only move inside the rectangle; otherwise, it will change the script $ s $ as follows:

- If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
- If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).

Then, it will execute the changed script starting from the character which it couldn't execute.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F2/ff49f6aa11a19418f77260f4c00c02fa1a42de65.png) An example of the robot's movement process, $ s = \texttt{"ULULURD"} $ The script $ s $ will be executed for $ k $ times continuously. All changes to the string $ s $ will be retained even when it is repeated. During this process, how many times will the robot move to the point $ (0, 0) $ in total? Note that the initial position does NOT count.

## 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 four integers $ n $ , $ k $ , $ w $ , and $ h $ ( $ 1 \le n, w, h \le 10^6 $ ; $ 1 \le k \le 10^{12} $ ).

The second line contains a single string $ s $ of size $ n $ ( $ s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\} $ ) — the script to be executed.

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

## Output Format

For each test case, print a single integer — the number of times the robot reaches $ (0, 0) $ when executing script $ s $ for $ k $ times continuously.

## Sample #1

### Sample Input #1

```
6
2 4 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 6 3 3
RUURD
7 5 3 4
RRDLUUU
7 123456789999 3 2
ULULURD
```

### Sample Output #1

```
1
4
3
1
1
41152263332
```

## Hint

In the first test case, the robot only moves up and right for the first two executions. After that, it occupies the position $ (2, 2) $ . For the next two executions, it moves down and left and finishes at $ (0, 0) $ . So the answer is $ 1 $ .

In the second test case, each time executing the script the robot visits the origin twice. And since $ k=2 $ , it visits the origin $ 2 \cdot 2 = 4 $ times overall.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F2/4c04dc66914a3e1ee672ced7111b24a5891eec80.png)In the third test case, the visualization is shown as below:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F2/354b17fd45a6d2914b35f5325993193690563e94.png)

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: chinese remainder theorem, math, number theory
Difficulty: 2800
# Dyn-scripted Robot (Easy Version)

## Problem Description

This is the easy version of the problem. The only difference is that in this version $ k \le n $ . You can make hacks only if both versions of the problem are solved.

Given a $ w \times h $ rectangle on the $ Oxy $ plane, with points $ (0, 0) $ at the bottom-left and $ (w, h) $ at the top-right of the rectangle.

You also have a robot initially at point $ (0, 0) $ and a script $ s $ of $ n $ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.

The robot can only move inside the rectangle; otherwise, it will change the script $ s $ as follows:

- If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
- If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).

Then, it will execute the changed script starting from the character which it couldn't execute.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F1/ff49f6aa11a19418f77260f4c00c02fa1a42de65.png) An example of the robot's movement process, $ s = \texttt{"ULULURD"} $ The script $ s $ will be executed for $ k $ times continuously. All changes to the string $ s $ will be retained even when it is repeated. During this process, how many times will the robot move to the point $ (0, 0) $ in total? Note that the initial position does NOT count.

## 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 four integers $ n $ , $ k $ , $ w $ , and $ h $ ( $ 1 \le n, w, h \le 10^6 $ ; $ 1 \le k \le n $ ).

The second line contains a single string $ s $ of size $ n $ ( $ s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\} $ ) — the script to be executed.

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

## Output Format

For each test case, print a single integer — the number of times the robot reaches $ (0, 0) $ when executing script $ s $ for $ k $ times continuously.

## Sample #1

### Sample Input #1

```
5
2 2 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 5 3 3
RUURD
7 5 3 4
RRDLUUU
```

### Sample Output #1

```
0
4
3
0
1
```

## Hint

In the first test case, the robot only moves up and right. In the end, it occupies the position $ (2, 2) $ but never visits $ (0, 0) $ . So the answer is $ 0 $ .

In the second test case, each time executing the script the robot visits the origin twice. And since $ k=2 $ , it visits the origin $ 2 \cdot 2 = 4 $ times overall.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F1/4c04dc66914a3e1ee672ced7111b24a5891eec80.png)In the third test case, the visualization is shown as below:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1993F1/354b17fd45a6d2914b35f5325993193690563e94.png)

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, chinese remainder theorem, constructive algorithms, math, number theory
Difficulty: 2400
# Med-imize

## Problem Description

Given two positive integers $ n $ and $ k $ , and another array $ a $ of $ n $ integers.

In one operation, you can select any subarray of size $ k $ of $ a $ , then remove it from the array without changing the order of other elements. More formally, let $ (l, r) $ be an operation on subarray $ a_l, a_{l+1}, \ldots, a_r $ such that $ r-l+1=k $ , then performing this operation means replacing $ a $ with $ [a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n] $ .

For example, if $ a=[1,2,3,4,5] $ and we perform operation $ (3,5) $ on this array, it will become $ a=[1,2] $ . Moreover, operation $ (2, 4) $ results in $ a=[1,5] $ , and operation $ (1,3) $ results in $ a=[4,5] $ .

You have to repeat the operation while the length of $ a $ is greater than $ k $ (which means $ |a| \gt k $ ). What is the largest possible median $ ^\dagger $ of all remaining elements of the array $ a $ after the process?

 $ ^\dagger $ The median of an array of length $ n $ is the element whose index is $ \left \lfloor (n+1)/2 \right \rfloor $ after we sort the elements in non-decreasing order. For example: $ median([2,1,5,4,3]) = 3 $ , $ median([5]) = 5 $ , and $ median([6,8,2,4]) = 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 two integers $ n $ and $ k $ ( $ 1 \le n, k \le 5 \cdot 10^5 $ ).

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ .

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

## Output Format

For each test case, print a single integer — the largest median possible after performing the operations.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
3
4
9
6
4
```

## Hint

In the first test case, you can select a subarray $ (l, r) $ which can be either $ (1, 3) $ or $ (2, 4) $ . Thus, two obtainable final arrays are $ [3] $ and $ [2] $ . The former one has the larger median ( $ 3 > 2 $ ) so the answer is $ 3 $ .

In the second test case, three obtainable final arrays are $ [6, 4] $ , $ [3, 4] $ , and $ [3, 2] $ . Their medians are $ 4 $ , $ 3 $ , and $ 2 $ respectively. The answer is $ 4 $ .

In the third test case, only one element is left in the final array and it can be any element of the initial array. The largest one among them is $ 9 $ , so the answer is $ 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, dp, greedy
Difficulty: 2200
# Light Switches

## Problem Description

There is an apartment consisting of $ n $ rooms, each with its light initially turned off.

To control the lights in these rooms, the owner of the apartment decided to install chips in the rooms so that each room has exactly one chip, and the chips are installed at different times. Specifically, these times are represented by the array $ a_1, a_2, \ldots, a_n $ , where $ a_i $ is the time (in minutes) at which a chip is installed in the $ i $ -th room.

As soon as a chip is installed, it changes the room's light status every $ k $ minutes — it turns on the light for $ k $ minutes, then turns it off for the next $ k $ minutes, then turns it back on for the next $ k $ minutes, and so on. In other words, the light status is changed by the chip at minute $ a_i $ , $ a_i + k $ , $ a_i + 2k $ , $ a_i + 3k $ , $ \ldots $ for the $ i $ -th room.

What is the earliest moment when all rooms in the apartment have their lights turned on?

## 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 k \le n \le 2 \cdot 10^5 $ ) — the number of rooms in the apartment and the period of the chips.

The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the moments when the chips are installed.

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, print a single integer — the answer to the question (in minutes). If there is no such moment that the lights are turned on in all the rooms, print $ -1 $ instead.

## Sample #1

### Sample Input #1

```
9
4 4
2 3 4 5
4 3
2 3 4 5
4 3
3 4 8 9
3 3
6 2 1
1 1
1
7 5
14 34 6 25 46 7 17
6 5
40 80 99 60 90 50
6 5
64 40 50 68 70 10
2 1
1 1000000000
```

### Sample Output #1

```
5
-1
10
8
1
47
100
-1
-1
```

## Hint

In the first test case, all lights will be on by the minute $ 5 $ without any of them being turned off by the chips. The answer is $ 5 $ .

In the second test case, due to $ k=3 $ , the $ 1 $ -st light will be on at minutes $ 2, 3, 4, 8, 9, 10, 14, \ldots $ ; meanwhile, the $ 4 $ -th light will be on at minutes $ 5, 6, 7, 11, 12, 13, 17, \ldots $ . These two sequences don't have any number in common, so they will never be on at the same time.

In the third test case, it can be seen that the $ 1 $ -st and $ 2 $ -nd lights will be turned off at minutes $ 6 $ and $ 7 $ , but the chips will turn them back on at minutes $ 9 $ and $ 10 $ . The $ 3 $ -rd and $ 4 $ -th lights will also be on at minute $ 10 $ , so the answer is $ 10 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 1400
# Parity and Sum

## Problem Description

Given an array $ a $ of $ n $ positive integers.

In one operation, you can pick any pair of indexes $ (i, j) $ such that $ a_i $ and $ a_j $ have distinct parity, then replace the smaller one with the sum of them. More formally:

- If $ a_i < a_j $ , replace $ a_i $ with $ a_i + a_j $ ;
- Otherwise, replace $ a_j $ with $ a_i + a_j $ .

Find the minimum number of operations needed to make all elements of the array have the same parity.

## 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 second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of array $ a $ .

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 a single integer — the minimum number of operations required.

## Sample #1

### Sample Input #1

```
7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000
```

### Sample Output #1

```
0
0
2
4
3
3
3
```

## Hint

In the first test case, all integers already have the same parity. Therefore, no operation is needed.

In the third test case, we can perform two operations $ (1, 2) $ and $ (1, 3) $ . The array $ a $ transforms as follows: $ a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9] $ .

In the fourth test case, an example of an optimal sequence of operations is $ (1, 2) $ , $ (1, 3) $ , $ (1, 4) $ , and $ (1, 4) $ . The array $ a $ transforms as follows: $ a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19] $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy
Difficulty: 1100
# Question Marks

## Problem Description

Tim is doing a test consisting of $ 4n $ questions; each question has $ 4 $ options: 'A', 'B', 'C', and 'D'. For each option, there are exactly $ n $ correct answers corresponding to that option — meaning there are $ n $ questions with the answer 'A', $ n $ questions with the answer 'B', $ n $ questions with the answer 'C', and $ n $ questions with the answer 'D'.

For each question, Tim wrote his answer on the answer sheet. If he could not figure out the answer, he would leave a question mark '?' for that question.

You are given his answer sheet of $ 4n $ characters. What is the maximum number of correct answers Tim can get?

## Input Format

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

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

The second line of each test case contains a string $ s $ of $ 4n $ characters ( $ s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, \texttt{?}\} $ ) — Tim's answers for the questions.

## Output Format

For each test case, print a single integer — the maximum score that Tim can achieve.

## Sample #1

### Sample Input #1

```
6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C
```

### Sample Output #1

```
4
2
4
0
9
13
```

## Hint

In the first test case, there is exactly one question with each answer 'A', 'B', 'C', and 'D'; so it's possible that Tim gets all his answers correct.

In the second test case, there are only two correct answers 'A' which makes him get exactly $ 2 $ points in any case.

In the third test case, Tim can get at most $ 2 $ correct answers with option 'A' and $ 2 $ correct answers with option 'B'. For example, he would get $ 4 $ points if the answers were 'AACCBBDD'.

In the fourth test case, he refuses to answer any question at all, which makes him get $ 0 $ points.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Ultra-Meow

## Problem Description

K1o0n gave you an array $ a $ of length $ n $ , consisting of numbers $ 1, 2, \ldots, n $ . Accept it? Of course! But what to do with it? Of course, calculate $ \text{MEOW}(a) $ .

Let $ \text{MEX}(S, k) $ be the $ k $ -th positive (strictly greater than zero) integer in ascending order that is not present in the set $ S $ . Denote $ \text{MEOW}(a) $ as the sum of $ \text{MEX}(b, |b| + 1) $ , over all distinct subsets $ b $ of the array $ a $ .

Examples of $ \text{MEX}(S, k) $ values for sets:

- $ \text{MEX}(\{3,2\}, 1) = 1 $ , because $ 1 $ is the first positive integer not present in the set;
- $ \text{MEX}(\{4,2,1\}, 2) = 5 $ , because the first two positive integers not present in the set are $ 3 $ and $ 5 $ ;
- $ \text{MEX}(\{\}, 4) = 4 $ , because there are no numbers in the empty set, so the first $ 4 $ positive integers not present in it are $ 1, 2, 3, 4 $ .

## Input Format

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

In a single line of each test case, an integer $ n $ ( $ 1 \le n \le 5000 $ ) is entered, the size of the array of gifted numbers.

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

## Output Format

For each test case, output a single number — $ \text{MEOW}(a) $ . Since it may be very large, output it modulo $ 10^9 + 7 $ .

## Sample #1

### Sample Input #1

```
5
2
3
4999
5
1
```

### Sample Output #1

```
12
31
354226409
184
4
```

## Limit



Time Limit
2.50s

Memory Limit
250.00MB

Tags: combinatorics, dp, math
Difficulty: 2000
# Valuable Cards

## Problem Description

In his favorite cafe Kmes once again wanted to try the herring under a fur coat. Previously, it would not have been difficult for him to do this, but the cafe recently introduced a new purchasing policy.

Now, in order to make a purchase, Kmes needs to solve the following problem: $ n $ cards with prices for different positions are laid out in front of him, on the $ i $ -th card there is an integer $ a_i $ , among these prices there is no whole positive integer $ x $ .

Kmes is asked to divide these cards into the minimum number of bad segments (so that each card belongs to exactly one segment). A segment is considered bad if it is impossible to select a subset of cards with a product equal to $ x $ . All segments, in which Kmes will divide the cards, must be bad.

Formally, the segment $ (l, r) $ is bad if there are no indices $ i_1 < i_2 < \ldots < i_k $ such that $ l \le i_1, i_k \le r $ , and $ a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = x $ .

Help Kmes determine the minimum number of bad segments in order to enjoy his favorite dish.

## Input Format

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

The first line of each set of input data gives you $ 2 $ integers $ n $ and $ x $ ( $ 1 \le n \le 10^5, 2 \le x \le 10^5 $ ) — the number of cards and the integer, respectively.

The second line of each set of input data contains $ n $ integers $ a_i $ ( $ 1 \le a_i \le 2 \cdot 10^5, a_i \neq x $ ) — the prices on the cards.

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

## Output Format

For each set of input data, output the minimum number of bad segments.

## Sample #1

### Sample Input #1

```
8
6 4
2 3 6 2 1 2
9 100000
50000 25000 12500 6250 3125 2 4 8 16
5 2
1 1 1 1 1
8 6
4 3 4 3 4 3 4 3
7 12
6 11 1 3 11 10 2
10 5
2 4 4 2 4 4 4 3 1 1
7 8
4 6 5 1 2 4 1
8 27
3 9 17 26 2 20 9 3
```

### Sample Output #1

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

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: brute force, dp, greedy, number theory, two pointers
Difficulty: 1900
# Novice's Mistake

## Problem Description

One of the first programming problems by K1o0n looked like this: "Noobish\_Monk has $ n $ $ (1 \le n \le 100) $ friends. Each of them gave him $ a $ $ (1 \le a \le 10000) $ apples for his birthday. Delighted with such a gift, Noobish\_Monk returned $ b $ $ (1 \le b \le \min(10000, a \cdot n)) $ apples to his friends. How many apples are left with Noobish\_Monk?"

K1o0n wrote a solution, but accidentally considered the value of $ n $ as a string, so the value of $ n \cdot a - b $ was calculated differently. Specifically:

- when multiplying the string $ n $ by the integer $ a $ , he will get the string $ s=\underbrace{n + n + \dots + n + n}_{a\ \text{times}} $
- when subtracting the integer $ b $ from the string $ s $ , the last $ b $ characters will be removed from it. If $ b $ is greater than or equal to the length of the string $ s $ , it will become empty.

Learning about this, ErnKor became interested in how many pairs $ (a, b) $ exist for a given $ n $ , satisfying the constraints of the problem, on which K1o0n's solution gives the correct answer.

"The solution gives the correct answer" means that it outputs a non-empty string, and this string, when converted to an integer, equals the correct answer, i.e., the value of $ n \cdot a - b $ .

## Input Format

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

For each test case, a single line of input contains an integer $ n $ ( $ 1 \le n \le 100 $ ).

It is guaranteed that in all test cases, $ n $ is distinct.

## Output Format

For each test case, output the answer in the following format:

In the first line, output the integer $ x $ — the number of bad tests for the given $ n $ .

In the next $ x $ lines, output two integers $ a_i $ and $ b_i $ — such integers that K1o0n's solution on the test " $ n $ $ a_i $ $ b_i $ " gives the correct answer.

## Sample #1

### Sample Input #1

```
3
2
3
10
```

### Sample Output #1

```
3
20 18 
219 216 
2218 2214 
1
165 162 
1
1262 2519
```

## Hint

In the first example, $ a = 20 $ , $ b = 18 $ are suitable, as " $ \text{2} $ " $ \cdot 20 - 18 = $ " $ \text{22222222222222222222} $ " $ - 18 = 22 = 2 \cdot 20 - 18 $

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, implementation, math, strings
Difficulty: 1700