yl-9/probench huggingface dataset:
# Alya and Permutation

## Problem Description

Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her.

Given an integer $ n $ , construct a permutation $ p $ of integers $ 1, 2, \ldots, n $ that maximizes the value of $ k $ (which is initially $ 0 $ ) after the following process.

Perform $ n $ operations, on the $ i $ -th operation ( $ i=1, 2, \dots, n $ ),

- If $ i $ is odd, $ k=k\,\&\,p_i $ , where $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).
- If $ i $ is even, $ k=k\,|\,p_i $ , where $ | $ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

## Input Format

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

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

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 $ in the first line and output the permutation $ p_1, p_2,\ldots, p_n $ in the second line.

If there are multiple such permutations, output any.

## Sample #1

### Sample Input #1

```
6
5
6
7
8
9
10
```

### Sample Output #1

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

## Hint

For the first test case, the value of $ k $ is determined as follows:

 $ k = 0 $ initially.

- On the $ 1 $ st operation, $ 1 $ is odd, so Alya sets $ k $ to be $ k\&p_1 = 0\&2 = 0 $ .
- On the $ 2 $ nd operation, $ 2 $ is even, so Alya sets $ k $ to be $ k|p_2 = 0|1 = 1 $ .
- On the $ 3 $ rd operation, $ 3 $ is odd, so Alya sets $ k $ to be $ k\&p_3 = 1\&3 = 1 $ .
- On the $ 4 $ th operation, $ 4 $ is even, so Alya sets $ k $ to be $ k|p_4 = 1|4 = 5 $ .
- On the $ 5 $ th operation, $ 5 $ is odd, so Alya sets $ k $ to be $ k\&p_5 = 5\&5 = 5 $ .

The final value of $ k $ is $ 5 $ . It can be shown that the final value of $ k $ is at most $ 5 $ for all permutations of length $ 5 $ . Another valid output is $ [2, 3, 1, 4, 5] $ .

For the second test case, the final value of $ k $ is $ 7 $ . It can be shown that the final value of $ k $ is at most $ 7 $ for all permutations of length $ 6 $ . Other valid outputs include $ [2, 4, 1, 6, 3, 5] $ and $ [5, 2, 6, 1, 3, 4] $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, constructive algorithms, math
Difficulty: 1400
# Everyone Loves Tres

## Problem Description

There are 3 heroes and 3 villains, so 6 people in total.



Given a positive integer $ n $ . Find the smallest integer whose decimal representation has length $ n $ and consists only of $ 3 $ s and $ 6 $ s such that it is divisible by both $ 33 $ and $ 66 $ . If no such integer exists, print $ -1 $ .

## Input Format

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

The only line of each test case contains a single integer $ n $ ( $ 1\le n\le 500 $ ) — the length of the decimal representation.

## Output Format

For each test case, output the smallest required integer if such an integer exists and $ -1 $ otherwise.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
-1
66
-1
3366
36366
3336366
```

## Hint

For $ n=1 $ , no such integer exists as neither $ 3 $ nor $ 6 $ is divisible by $ 33 $ .

For $ n=2 $ , $ 66 $ consists only of $ 6 $ s and it is divisible by both $ 33 $ and $ 66 $ .

For $ n=3 $ , no such integer exists. Only $ 363 $ is divisible by $ 33 $ , but it is not divisible by $ 66 $ .

For $ n=4 $ , $ 3366 $ and $ 6666 $ are divisible by both $ 33 $ and $ 66 $ , and $ 3366 $ is the smallest.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math, number theory
Difficulty: 900
# Sliding

## Problem Description

Red was ejected. They were not the imposter.



There are $ n $ rows of $ m $ people. Let the position in the $ r $ -th row and the $ c $ -th column be denoted by $ (r, c) $ . Number each person starting from $ 1 $ in row-major order, i.e., the person numbered $ (r-1)\cdot m+c $ is initially at $ (r,c) $ .

The person at $ (r, c) $ decides to leave. To fill the gap, let the person who left be numbered $ i $ . Each person numbered $ j>i $ will move to the position where the person numbered $ j-1 $ is initially at. The following diagram illustrates the case where $ n=2 $ , $ m=3 $ , $ r=1 $ , and $ c=2 $ .

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2035A/958314060b9182d5223494dfb5da32d06c99cb0a.png)Calculate the sum of the Manhattan distances of each person's movement. If a person was initially at $ (r_0, c_0) $ and then moved to $ (r_1, c_1) $ , the Manhattan distance is $ |r_0-r_1|+|c_0-c_1| $ .

## 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 testcase contains $ 4 $ integers $ n $ , $ m $ , $ r $ , and $ c $ ( $ 1\le r\le n\le 10^6 $ , $ 1 \le c \le m \le 10^6 $ ), where $ n $ is the number of rows, $ m $ is the number of columns, and $ (r,c) $ is the position where the person who left is initially at.

## Output Format

For each test case, output a single integer denoting the sum of the Manhattan distances.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
6
1
0
1999998000000
```

## Hint

For the first test case, the person numbered $ 2 $ leaves, and the distances of the movements of the person numbered $ 3 $ , $ 4 $ , $ 5 $ , and $ 6 $ are $ 1 $ , $ 3 $ , $ 1 $ , and $ 1 $ , respectively. So the answer is $ 1+3+1+1=6 $ .

For the second test case, the person numbered $ 3 $ leaves, and the person numbered $ 4 $ moves. The answer is $ 1 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 800
# Rayan vs. Rayaneh

## Problem Description

Rayan makes his final efforts to win Reyhaneh's heart by claiming he is stronger than Rayaneh (i.e., computer in Persian). To test this, Reyhaneh asks [Khwarizmi](https://en.wikipedia.org/wiki/Al-Khwarizmi) for help. Khwarizmi explains that a set is integer linearly independent if no element in the set can be written as an integer linear combination of the others. Rayan is given a set of integers each time and must identify one of the largest possible integer linearly independent subsets.

Note that a single element is always considered an integer linearly independent subset.

An integer linearly combination of $ a_1, \ldots, a_k $ is any sum of the form $ c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k $ where $ c_1, c_2, \ldots, c_k $ are integers (which may be zero, positive, or negative).

## Input Format

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

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^5 $ ), the size of the set. The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ).

The sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^6 $ .

## Output Format

In the first line of each test case print the size of the largest integer linearly independent subset.

In the next line, print one such subset in any order. If there are multiple valid subsets, print any one of them.

## Sample #1

### Sample Input #1

```
3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6
```

### Sample Output #1

```
2
4 6
3
35 21 30
2
2 3
```

## Hint

In example 1, $ \{4, 6\} $ is an integer linearly independent subset. It can be proven that there is no integer linearly independent subset with at least $ 3 $ elements.

In example 2, $ \{35, 21, 30\} $ is an integer linearly independent subset because no integer linear combination of any two elements can create the third. There is no integer linearly independent subset with at least $ 4 $ elements.

In example 3, $ \{2, 3, 6\} $ is not an integer linearly independent subset since $ 6 $ can be written as $ 6 \cdot 2 + (-2) \cdot 3 $ , which is an integer linear combination of $ \{2, 3\} $ .

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: brute force, dfs and similar, dp, number theory
Difficulty: 3300
# Simurgh's Watch (Hard Version)

## Problem Description

The only difference between the two versions of the problem is whether overlaps are considered at all points or only at integer points.

The legendary [Simurgh](https://www.eavartravel.com/blog/2023/11/3/140727/simurgh/), a mythical bird, is responsible for keeping watch over vast lands, and for this purpose, she has enlisted $ n $ vigilant warriors. Each warrior is alert during a specific time segment $ [l_i, r_i] $ , where $ l_i $ is the start time (included) and $ r_i $ is the end time (included), both positive integers.

 ![](https://espresso.codeforces.com/e448e919c3f03a9c212cd45c8dcd8e2bb0be579c.webp)One of Simurgh's trusted advisors, [Zal](https://asia-archive.si.edu/learn/shahnama/zal-and-the-simurgh/), is concerned that if multiple warriors are stationed at the same time and all wear the same color, the distinction between them might be lost, causing confusion in the watch. To prevent this, whenever multiple warriors are on guard at the same integer moment, there must be at least one color which is worn by exactly one warrior.

So the task is to determine the minimum number of colors required and assign a color $ c_i $ to each warrior's segment $ [l_i, r_i] $ such that, for every (integer) time $ t $ contained in at least one segment, there exists one color which belongs to exactly one segment containing $ t $ .

## Input Format

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

For each test case:

- The first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of warriors stationed by Simurgh.
- The next $ n $ lines each contain two integers $ l_i $ and $ r_i $ ( $ 1 \leq l_i \leq r_i \leq 10^9 $ ) — the start and end times of the warrior's watch segment.

The sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case:

- Output the minimum number of colors $ k $ needed.
- Then, output a line of $ n $ integers $ c_i $ ( $ 1 \leq c_i \leq k $ ), where each $ c_i $ is the color assigned to the $ i $ -th warrior.

## Sample #1

### Sample Input #1

```
3
5
1 4
2 8
3 7
5 10
6 9
5
1 5
2 6
3 7
4 7
6 7
5
4 9
8 17
2 15
12 19
6 13
```

### Sample Output #1

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

## Hint

We can represent each warrior's watch segment as an interval on the X-axis;

In test case 1, the intervals can be colored as shown below (intervals are colored with the selected color; areas are colored if this color occurs exactly once at this point in time):

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2034G2/a8ca04e863ed852cb4b11c3982c1d5442199b24b.png)In test case 2, the intervals can be colored as shown below:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2034G2/36f2a5d9878f69668f835178da7df8642bec8342.png)In test case 3, the intervals can be colored as shown below:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2034G2/75559577acf19732a5a59981d3806145e52c5ed5.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 3500
# Permutations Harmony

## Problem Description

Rayan wants to present a gift to Reyhaneh to win her heart. However, Reyhaneh is particular and will only accept a k-harmonic set of permutations.

We define a k-harmonic set of permutations as a set of $ k $ pairwise distinct permutations $ p_1, p_2, \ldots, p_k $ of size $ n $ such that for every pair of indices $ i $ and $ j $ (where $ 1 \leq i, j \leq n $ ), the following condition holds:

 $ $$$ p_1[i] + p_2[i] + \ldots + p_k[i] = p_1[j] + p_2[j] + \ldots + p_k[j]  $ $ </p><p>Your task is to help Rayan by either providing a valid <span class="tex-font-style-it">k-harmonic set of permutations</span> for given values of  $ n $  and  $ k $  or by determining that such a set does not exist.</p><p>We call a sequence of length  $ n $  a permutation if it contains every integer from  $ 1 $  to  $ n$$$ exactly once.

## Input Format

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

Each test case consists of two integers $ n $ and $ k $ ( $ 1 \leq n, k \leq 10^5 $ ). The sum of $ n \cdot k $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

## Output Format

For each test case, if a k-harmonic set of permutations exists, print YES on the first line. Then, print $ k $ lines, each containing a distinct permutation of the integers from $ 1 $ to $ n $ .

If no such set exists, print NO on the first line.

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

If multiple answers are possible, you can output any of them.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
YES
1 2 3
2 3 1
3 1 2
YES
1 2 3 4
4 3 2 1
NO
YES
1 2 3
3 2 1
```

## Hint

In example 1, we have $ p_1 = [1, 2, 3] $ , $ p_2 = [2, 3, 1] $ , and $ p_3 = [3, 1, 2] $ . It's easy to see that $ p_1[1] + p_2[1] + p_3[1] = p_1[2] + p_2[2] + p_3[2] = p_1[3] + p_2[3] + p_3[3] = 6 $ .

In example 2, we have $ p_1 = [1, 2, 3, 4] $ and $ p_2 = [4, 3, 2, 1] $ . It's easy to see that $ p_1[1] + p_2[1] = p_1[2] + p_2[2] = p_1[3] + p_2[3] = p_1[4] + p_2[4] = 5 $ .

In example 3, as there are five distinct elements in $ p_1 $ , it's obvious that the answer is "No".

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, constructive algorithms, greedy, hashing, math
Difficulty: 2200
# Darius' Wisdom

## Problem Description

[Darius the Great](https://en.wikipedia.org/wiki/Darius_the_Great) is constructing $ n $ stone columns, each consisting of a base and between $ 0 $ , $ 1 $ , or $ 2 $ inscription pieces stacked on top.

In each move, Darius can choose two columns $ u $ and $ v $ such that the difference in the number of inscriptions between these columns is exactly $ 1 $ , and transfer one inscription from the column with more inscriptions to the other one. It is guaranteed that at least one column contains exactly $ 1 $ inscription.

 ![](https://espresso.codeforces.com/d4cdf6815b1220ffe2be57e8bcb7d42bfa773cfc.webp)Since beauty is the main pillar of historical buildings, Darius wants the columns to have ascending heights. To avoid excessive workers' efforts, he asks you to plan a sequence of at most $ n $  moves to arrange the columns in non-decreasing order based on the number of inscriptions. Minimizing the number of moves is not required.

## Input Format

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

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

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ , where $ a_i \in \{0,1,2\} $ represents the initial number of inscriptions in the $ i $ -th column. It is guaranteed that at least one column has exactly $ 1 $ inscription.

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 an integer $ k $ — the number of moves used to sort the columns. ( $ 0 \leq k \leq n $ )

Then, output $ k $ lines, each containing two integers $ u_i $ and $ v_i $ ( $ 1 \leq u_i, v_i \leq n $ ), representing the indices of the columns involved in the $ i $ -th move. During each move, it must hold that $ |a_{u_i} - a_{v_i}| = 1 $ , and one inscription is transferred from the column with more inscriptions to the other.

It can be proven that a valid solution always exists under the given constraints.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

Columns state in the first test case:

- Initial: $ 0, 2, 0, 1 $
- After the first move: $ 0, 1, 0, 2 $
- After the second move: $ 0, 0, 1, 2 $

Columns state in the second test case:

- Initial: $ 1, 2, 0 $
- After the first move: $ 0, 2, 1 $
- After the second move: $ 0, 1, 2 $

In the third test case, the column heights are already sorted in ascending order.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, implementation, sortings
Difficulty: 1600
# Trapped in the Witch's Labyrinth

## Problem Description

In the [fourth labor of Rostam](https://www.gathertales.com/story/the-tale-of-the-haft-khan-seven-labors-of-rostam/sid-604), the legendary hero from the [Shahnameh](https://en.wikipedia.org/wiki/Shahnameh), an old witch has created a magical maze to trap him. The maze is a rectangular grid consisting of $ n $ rows and $ m $ columns. Each cell in the maze points in a specific direction: up, down, left, or right. The witch has enchanted Rostam so that whenever he is in a cell, he will move to the next cell in the direction indicated by that cell.

 ![](https://espresso.codeforces.com/fe31b399bb2207f13616c91f5553e04c54d77805.webp)If Rostam eventually exits the maze, he will be freed from the witch's enchantment and will defeat her. However, if he remains trapped within the maze forever, he will never escape.

The witch has not yet determined the directions for all the cells. She wants to assign directions to the unspecified cells in such a way that the number of starting cells from which Rostam will be trapped forever is maximized. Your task is to find the maximum number of starting cells which make Rostam trapped.

## Input Format

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

For each test case:

- The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 1000 $ ), representing the number of rows and columns in the maze.
- Each of the next $ n $ lines contains a string of $ m $ characters representing the directions in the maze. Each character is one of the following: 
  - U (up)
  - D (down)
  - L (left)
  - R (right)
  - ? (unspecified direction)

It's guaranteed that the sum of $ n \cdot m $ over all test cases is at most $ 10^6 $ .

## Output Format

For each test case, print a single integer, the maximum number of starting cells from which Rostam will be trapped forever after assigning directions to the unspecified cells optimally.

## Sample #1

### Sample Input #1

```
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL
```

### Sample Output #1

```
0
6
5
```

## Hint

In the first test case, all of the cells will be good no matter what you do.

In the second test case, if you assign the ?s like the picture below, all of the cells will be bad:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2034C/03527f7c6dbf693b9ca57b1f366ff7e58f4c6374.png)In the third test case, if you assign the ?s like the picture below, you will have $ 5 $ bad cells (red-shaded cells):

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2034C/0aeb2b1c56e61e1ba503a6b9771234d76ab5289a.png)

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: constructive algorithms, dfs and similar, graphs, implementation
Difficulty: 1400
# Rakhsh's Revival

## Problem Description

[Rostam](https://en.wikipedia.org/wiki/Rostam)'s loyal horse, [Rakhsh](https://en.wikipedia.org/wiki/Rakhsh), has seen better days. Once powerful and fast, Rakhsh has grown weaker over time, struggling to even move. Rostam worries that if too many parts of Rakhsh's body lose strength at once, Rakhsh might stop entirely. To keep his companion going, Rostam decides to strengthen Rakhsh, bit by bit, so no part of his body is too frail for too long.

 ![](https://espresso.codeforces.com/ace389a4376151924b6a103ba086e314fbadc855.webp)Imagine Rakhsh's body as a line of spots represented by a binary string $ s $ of length $ n $ , where each $ 0 $ means a weak spot and each $ 1 $ means a strong one. Rostam's goal is to make sure that no interval of $ m $ consecutive spots is entirely weak (all $ 0 $ s).

Luckily, Rostam has a special ability called Timar, inherited from his mother [Rudabeh](https://en.wikipedia.org/wiki/Rudaba) at birth. With Timar, he can select any segment of length $ k $ and instantly strengthen all of it (changing every character in that segment to $ 1 $ ). The challenge is to figure out the minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $ m $ .

## Input Format

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

The first line of each test case contains three numbers $ n $ , $ m $ , $ k $ ( $ 1 \le m, k \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains a binary string $ s $ of $ n $ characters $ s_1s_2 \ldots s_n $ . ( $ s_i \in \{ $ 0,1 $ \} $ for $ 1 \le i \le n $ ).

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 minimum number of times Rostam needs to use Timar to keep Rakhsh moving, ensuring there are no consecutive entirely weak spots of length $ m $ .

## Sample #1

### Sample Input #1

```
3
5 1 1
10101
5 2 1
10101
6 3 2
000000
```

### Sample Output #1

```
2
0
1
```

## Hint

In the first test case, we should apply an operation on each 0.

In the second test case, $ s $ is already ok.

In the third test case, we can perform an operation on interval $ [3,4] $ to get 001100.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: data structures, greedy, implementation, two pointers
Difficulty: 1000
# King Keykhosrow's Mystery

## Problem Description

There is a tale about the wise [King Keykhosrow](https://en.wikipedia.org/wiki/Kay_Khosrow) who owned a grand treasury filled with treasures from across the Persian Empire. However, to prevent theft and ensure the safety of his wealth, King Keykhosrow's vault was sealed with a magical lock that could only be opened by solving a riddle.

 ![](https://espresso.codeforces.com/02ff1013de2c71e8f78fd7d74b43bd365dcc6a3b.webp)The riddle involves two sacred numbers $ a $ and $ b $ . To unlock the vault, the challenger must determine the smallest key number $ m $ that satisfies two conditions:

- $ m $ must be greater than or equal to at least one of $ a $ and $ b $ .
- The remainder when $ m $ is divided by $ a $ must be equal to the remainder when $ m $ is divided by $ b $ .

Only by finding the smallest correct value of $ m $ can one unlock the vault and access the legendary treasures!

## Input Format

The first line of the input contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ), the number of test cases.

Each test case consists of a single line containing two integers $ a $ and $ b $ ( $ 1 \leq a, b \leq 1000 $ ).

## Output Format

For each test case, print the smallest integer $ m $ that satisfies the conditions above.

## Sample #1

### Sample Input #1

```
2
4 6
472 896
```

### Sample Output #1

```
12
52864
```

## Hint

In the first test case, you can see that:

- $ 4 \bmod 4 = 0 $ but $ 4 \bmod 6 = 4 $
- $ 5 \bmod 4 = 1 $ but $ 5 \bmod 6 = 5 $
- $ 6 \bmod 4 = 2 $ but $ 6 \bmod 6 = 0 $
- $ 7 \bmod 4 = 3 $ but $ 7 \bmod 6 = 1 $
- $ 8 \bmod 4 = 0 $ but $ 8 \bmod 6 = 2 $
- $ 9 \bmod 4 = 1 $ but $ 9 \bmod 6 = 3 $
- $ 10 \bmod 4 = 2 $ but $ 10 \bmod 6 = 4 $
- $ 11 \bmod 4 = 3 $ but $ 11 \bmod 6 = 5 $

 so no integer less than $ 12 $ satisfies the desired properties.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, chinese remainder theorem, math, number theory
Difficulty: 800