yl-9/probench huggingface dataset:
# Adrenaline Rush

## Problem Description

Alice's friend is a big fan of the Adrenaline Rush racing competition and always strives to attend every race. However, this time, Alice is the one watching the race. To ensure her friend does not miss any important details, Alice decides to take notes on everything that happens on the track.

The first thing Alice notices before the race begins is the numbering of the cars. All the cars line up in front of the starting line in a specific order. The car closest to the line is numbered $ 1 $ , the second car is numbered $ 2 $ , and so on, up to the last car, which is numbered $ n $ . How convenient! — Alice thought.

The race begins with the countdown: "Three! Two! One! Go!". Alice observes that the cars start in their original order. However, as the race progresses, their order changes. She records whenever one car overtakes another, essentially swapping places with it on the track.

During the race, Alice notices something curious: no car overtakes another more than once. In other words, for any two cars $ x $ and $ y $ , there are at most two overtakes between them during the race: " $ x $ overtakes $ y $ " and/or " $ y $ overtakes $ x $ ".

At the end of the race, Alice carefully writes down the final order of the cars $ c_1, c_2, \ldots, c_n $ , where $ c_1 $ represents the winner of the race.

Alice's friend, however, is only interested in the final ranking and discards all of Alice's notes except for the final ordering. As Alice is quite curious, she wonders: What is the longest possible sequence of overtakes she could have observed during the race? Your task is to help Alice answer this question.

## Input Format

The first line of the input contains a single integer $ n\;(1 \le n \le 1000) $ — the number of cars in the race.

The second line contains a permutation $ c_1, c_2, \ldots, c_n\;(1 \le c_i \le n, c_i \ne c_j) $ — the final order of the cars.

## Output Format

The first line of the output should contain a single integer $ m $ — the maximum possible number of overtakes that can occur during the race.

Each of the next $ m $ lines should contain two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ) representing an overtake event, where car $ x $ overtakes car $ y $ . This means that car $ x $ was directly behind car $ y $ and overtakes it. The overtakes must be listed in the order they occurred during the race.

After all $ m $ overtakes have occurred, the cars must arrive at the finish line in the order $ c_1, c_2, \ldots, c_n $ . Note that any car $ x $ should not overtake another car $ y $ more than once.

If there are multiple possible longest sequences of overtakes, output any of them.

## Sample #1

### Sample Input #1

```
3
2 3 1
```

### Sample Output #1

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

## Sample #2

### Sample Input #2

```
1
1
```

### Sample Output #2

```
0
```

## Sample #3

### Sample Input #3

```
2
1 2
```

### Sample Output #3

```
2
2 1
1 2
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: constructive algorithms
Difficulty: 1600
# Snakes

## Problem Description

Suppose you play a game where the game field looks like a strip of $ 1 \times 10^9 $ square cells, numbered from $ 1 $ to $ 10^9 $ .

You have $ n $ snakes (numbered from $ 1 $ to $ n $ ) you need to place into some cells. Initially, each snake occupies exactly one cell, and you can't place more than one snake into one cell. After that, the game starts.

The game lasts for $ q $ seconds. There are two types of events that may happen each second:

- snake $ s_i $ enlarges: if snake $ s_i $ occupied cells $ [l, r] $ , it enlarges to a segment $ [l, r + 1] $ ;
- snake $ s_i $ shrinks: if snake $ s_i $ occupied cells $ [l, r] $ , it shrinks to a segment $ [l + 1, r] $ .

Each second, exactly one of the events happens.

If at any moment of time, any snake runs into some obstacle (either another snake or the end of the strip), you lose. Otherwise, you win with the score equal to the maximum cell occupied by any snake so far.

What is the minimum possible score you can achieve?

## Input Format

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 20 $ ; $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of snakes and the number of events. Next $ q $ lines contain the description of events — one per line.

The $ i $ -th line contains

- either " $ s_i $ +" ( $ 1 \le s_i \le n $ ) meaning that the $ s_i $ -th snake enlarges
- or " $ s_i $ -" ( $ 1 \le s_i \le n $ ) meaning that the $ s_i $ -th snake shrinks.

Additional constraint on the input: the given sequence of events is valid, i. e. a snake of length $ 1 $ never shrinks.

## Output Format

Print one integer — the minimum possible score.

## Sample #1

### Sample Input #1

```
3 6
1 +
1 -
3 +
3 -
2 +
2 -
```

### Sample Output #1

```
4
```

## Sample #2

### Sample Input #2

```
5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +
```

### Sample Output #2

```
11
```

## Hint

In the first test, the optimal strategy is to place the second snake at cell $ 1 $ , the third snake — at $ 2 $ , and the first one — at $ 3 $ . The maximum occupied cell is cell $ 4 $ , and it's the minimum possible score.

In the second test, one of the optimal strategies is to place:

- snake $ 2 $ at position $ 1 $ ;
- snake $ 3 $ at position $ 4 $ ;
- snake $ 5 $ at position $ 6 $ ;
- snake $ 1 $ at position $ 9 $ ;
- snake $ 4 $ at position $ 10 $ .

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: bitmasks, dp, dsu, graphs
# Joker

## Problem Description

Consider a deck of $ n $ cards. The positions in the deck are numbered from $ 1 $ to $ n $ from top to bottom. A joker is located at position $ m $ .

 $ q $ operations are applied sequentially to the deck. During the $ i $ -th operation, you need to take the card at position $ a_i $ and move it either to the beginning or to the end of the deck. For example, if the deck is $ [2, 1, 3, 5, 4] $ , and $ a_i=2 $ , then after the operation the deck will be either $ [1, 2, 3, 5, 4] $ (the card from the second position moved to the beginning) or $ [2, 3, 5, 4, 1] $ (the card from the second position moved to the end).

Your task is to calculate the number of distinct positions where the joker can be after each operation.

## 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 three integers $ n $ , $ m $ , and $ q $ ( $ 2 \le n \le 10^9 $ ; $ 1 \le m \le n $ ; $ 1 \le q \le 2 \cdot 10^5 $ ).

The second line contains $ q $ integers $ a_1, a_2, \dots, a_q $ ( $ 1 \le a_i \le n $ ).

Additional constraint on the input: the sum of $ q $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print $ q $ integers — the number of distinct positions where the joker can be after each operation.

## Sample #1

### Sample Input #1

```
5
6 5 3
1 2 3
2 1 4
2 1 1 2
5 3 1
3
3 2 4
2 1 1 1
18 15 4
13 15 1 16
```

### Sample Output #1

```
2 3 5 
2 2 2 2 
2 
2 3 3 3 
2 4 6 8
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, greedy, implementation, math
# Best Price

## Problem Description

A batch of Christmas trees has arrived at the largest store in Berland. $ n $ customers have already come to the store, wanting to buy them.

Before the sales begin, the store needs to determine the price for one tree (the price is the same for all customers). To do this, the store has some information about each customer.

For the $ i $ -th customer, two integers $ a_i $ and $ b_i $ are known, which define their behavior:

- if the price of the product is at most $ a_i $ , the customer will buy a tree and leave a positive review;
- otherwise, if the price of the product is at most $ b_i $ , the customer will buy a tree but leave a negative review;
- otherwise, the customer will not buy a tree at all.

Your task is to calculate the maximum possible earnings for the store, given that it can receive no more than $ k $ negative reviews.

## 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 $ ; $ 0 \le k \le n $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 2 \cdot 10^9 $ ).

The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 2 \cdot 10^9 $ ; $ a_i < b_i $ ).

Additional constraint on the input: 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 maximum possible earnings for the store, given that it can receive no more than $ k $ negative reviews.

## Sample #1

### Sample Input #1

```
5
2 0
2 1
3 4
1 1
2
5
3 3
1 5 2
3 6 4
4 3
2 3 2 8
3 7 3 9
3 1
2 9 5
12 14 9
```

### Sample Output #1

```
2
5
9
14
15
```

## Hint

Consider the example from the statement:

- In the first test case, the price should be set to $ 1 $ . Then both customers will buy one tree each and leave no negative reviews;
- In the second test case, the price should be set to $ 5 $ . Then the only customer will buy a tree and leave a negative review;
- In the third test case, the price should be set to $ 3 $ . Then all customers will buy one tree each, and the store will receive two negative reviews.
- In the fourth test case, the price should be set to $ 7 $ . Then two customers will buy one tree each, and the store will receive one negative review.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, brute force, data structures, greedy, sortings
# Counting Pairs

## Problem Description

You are given a sequence $ a $ , consisting of $ n $ integers, where the $ i $ -th element of the sequence is equal to $ a_i $ . You are also given two integers $ x $ and $ y $ ( $ x \le y $ ).

A pair of integers $ (i, j) $ is considered interesting if the following conditions are met:

- $ 1 \le i < j \le n $ ;
- if you simultaneously remove the elements at positions $ i $ and $ j $ from the sequence $ a $ , the sum of the remaining elements is at least $ x $ and at most $ y $ .

Your task is to determine the number of interesting pairs of integers for the given sequence $ a $ .

## Input Format

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

Each test case consists of two lines:

- The first line contains three integers $ n, x, y $ ( $ 3 \le n \le 2 \cdot 10^5 $ , $ 1 \le x \le y \le 2 \cdot 10^{14} $ );
- The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{9} $ ).

Additional constraint on the input: the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output one integer — the number of interesting pairs of integers for the given sequence $ a $ .

## Sample #1

### Sample Input #1

```
7
4 8 10
4 6 3 6
6 22 27
4 9 6 3 4 5
3 8 10
3 2 1
3 1 1
2 3 4
3 3 6
3 2 1
4 4 12
3 3 2 1
6 8 8
1 1 2 2 2 3
```

### Sample Output #1

```
4
7
0
0
1
5
6
```

## Hint

In the first example, there are $ 4 $ interesting pairs of integers:

1. $ (1, 2) $ ;
2. $ (1, 4) $ ;
3. $ (2, 3) $ ;
4. $ (3, 4) $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, sortings, two pointers
# Preparing for the Exam

## Problem Description

Monocarp is preparing for his first exam at the university. There are $ n $ different questions which can be asked during the exam, numbered from $ 1 $ to $ n $ . There are $ m $ different lists of questions; each list consists of exactly $ n-1 $ different questions. Each list $ i $ is characterized by one integer $ a_i $ , which is the index of the only question which is not present in the $ i $ -th list. For example, if $ n = 4 $ and $ a_i = 3 $ , the $ i $ -th list contains questions $ [1, 2, 4] $ .

During the exam, Monocarp will receive one of these $ m $ lists of questions. Then, the professor will make Monocarp answer all questions from the list. So, Monocarp will pass only if he knows all questions from the list.

Monocarp knows the answers for $ k $ questions $ q_1, q_2, \dots, q_k $ . For each list, determine if Monocarp will pass the exam if he receives that list.

## Input Format

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

Each test case consists of three lines:

- the first line contains three integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 3 \cdot 10^5 $ ; $ 1 \le m, k \le n $ );
- the second line contains $ m $ distinct integers $ a_1, a_2, \dots, a_m $ ( $ 1 \le a_i \le n $ ; $ a_i < a_{i+1} $ );
- the third line contains $ k $ distinct integers $ q_1, q_2, \dots, q_k $ ( $ 1 \le q_i \le n $ ; $ q_i < q_{i+1} $ ).

Additional constraints on the input:

- the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

## Output Format

For each test case, print a string of $ m $ characters. The $ i $ -th character should be 1 if Monocarp passes the exam if he receives the $ i $ -th question list, 0 if Monocarp won't pass.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0100
0000
1111
10
```

## Hint

In the first test case, Monocarp knows the questions $ [1, 3, 4] $ . Let's consider all the question lists:

- the first list consists of questions $ [2, 3, 4] $ . Monocarp doesn't know the $ 2 $ -nd question, so he won't pass;
- the second list consists of questions $ [1, 3, 4] $ . Monocarp knows all these questions, so he will pass;
- the third list consists of questions $ [1, 2, 4] $ . Monocarp doesn't know the $ 2 $ -nd question, so he won't pass;
- the fourth list consists of questions $ [1, 2, 3] $ . Monocarp doesn't know the $ 2 $ -nd question, so he won't pass.

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: constructive algorithms, implementation
# Journey

## Problem Description

Monocarp decided to embark on a long hiking journey.

He decided that on the first day he would walk $ a $ kilometers, on the second day he would walk $ b $ kilometers, on the third day he would walk $ c $ kilometers, on the fourth day, just like on the first, he would walk $ a $ kilometers, on the fifth day, just like on the second, he would walk $ b $ kilometers, on the sixth day, just like on the third, he would walk $ c $ kilometers, and so on.

Monocarp will complete his journey on the day when he has walked at least $ n $ kilometers in total. Your task is to determine the day on which Monocarp will complete his journey.

## Input Format

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

Each test case consists of one line containing four integers $ n $ , $ a $ , $ b $ , $ c $ ( $ 1 \le n \le 10^9 $ ; $ 1 \le a, b, c \le 10^6 $ ).

## Output Format

For each test case, output one integer — the day on which Monocarp will have walked at least $ n $ kilometers in total and will complete his journey.

## Sample #1

### Sample Input #1

```
4
12 1 5 3
6 6 7 4
16 3 4 1
1000000000 1 1 1
```

### Sample Output #1

```
5
1
6
1000000000
```

## Hint

In the first example, over the first four days, Monocarp will cover $ 1 + 5 + 3 + 1 = 10 $ kilometers. On the fifth day, he will cover another $ 5 $ kilometers, meaning that in total over five days he will have covered $ 10 + 5 = 15 $ kilometers. Since $ n = 12 $ , Monocarp will complete his journey on the fifth day.

In the second example, Monocarp will cover $ 6 $ kilometers on the first day. Since $ n = 6 $ , Monocarp will complete his journey on the very first day.

In the third example, Monocarp will cover $ 3 + 4 + 1 + 3 + 4 + 1 = 16 $ kilometers over the first six days. Since $ n = 16 $ , Monocarp will complete his journey on the sixth day.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, math
# Preparing for the Olympiad

## Problem Description

Monocarp and Stereocarp are preparing for the Olympiad. There are $ n $ days left until the Olympiad. On the $ i $ -th day, if Monocarp plans to practice, he will solve $ a_i $ problems. Similarly, if Stereocarp plans to practice on the same day, he will solve $ b_i $ problems.

Monocarp can train on any day he wants. However, Stereocarp watches Monocarp and follows a different schedule: if Monocarp trained on day $ i $ and $ i < n $ , then Stereocarp will train on day $ (i+1) $ .

Monocarp wants to organize his training process in a way that the difference between the number of problems he solves and the number of problems Stereocarp solves is as large as possible. Formally, Monocarp wants to maximize the value of $ (m-s) $ , where $ m $ is the number of problems he solves, and $ s $ is the number of problems Stereocarp solves. Help Monocarp determine the maximum possible difference in the number of solved problems between them.

## 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 test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 100 $ ).

The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le 100 $ ).

## Output Format

For each test case, print a single integer — the maximum possible difference between the number of problems Monocarp solves and the number of problems Stereocarp solves.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
4
5
1
16
```

## Hint

Let's analyze the example from the statement:

- In the first test case, it is optimal for Monocarp to train both days; then Stereocarp will train on day $ 2 $ .
- In the second test case, it is optimal for Monocarp to train on the only day, and Stereocarp will not train at all.
- In the third test case, it is optimal for Monocarp to train on the last day (and only on that day).
- In the fourth test case, it is optimal for Monocarp to train on days $ 1, 3, 4, 6 $ ; then Stereocarp will train on days $ 2, 4, 5 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy
# Tree Destruction

## Problem Description

Given a tree $ ^{\text{∗}} $ with $ n $ vertices. You can choose two vertices $ a $ and $ b $ once and remove all vertices on the path from $ a $ to $ b $ , including the vertices themselves. If you choose $ a=b $ , only one vertex will be removed.

Your task is to find the maximum number of connected components $ ^{\text{†}} $ that can be formed after removing the path from the tree.

 $ ^{\text{∗}} $ A tree is a connected graph without cycles.

 $ ^{\text{†}} $ A connected component is a set of vertices such that there is a path along the edges from any vertex to any other vertex in the set (and it is not possible to reach vertices not belonging to this set)

## Input Format

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

The first line of each test case contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the size of the tree.

The next $ n-1 $ lines contain two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \ne v $ ) — the vertices connected by an edge. It is guaranteed that the edges form a tree.

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 one integer — the maximum number of connected components that can be achieved using the described operation.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dfs and similar, dp, trees
Difficulty: 1900
# Maximum modulo equality

## Problem Description

You are given an array $ a $ of length $ n $ and $ q $ queries $ l $ , $ r $ .

For each query, find the maximum possible $ m $ , such that all elements $ a_l $ , $ a_{l+1} $ , ..., $ a_r $ are equal modulo $ m $ . In other words, $ a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m $ , where $ a \bmod b $ — is the remainder of division $ a $ by $ b $ . In particular, when $ m $ can be infinite, print $ 0 $ .

## 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 $ , $ q $ ( $ 1 \le n, q \le 2\cdot 10^5 $ ) — the length of the array and the number of queries.

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

In the following $ q $ lines of each test case, two integers $ l $ , $ r $ are provided ( $ 1 \le l \le r \le n $ ) — the range of the query.

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

## Output Format

For each query, output the maximum value $ m $ described in the statement.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

In the first query of the first sample, $ 6 \bmod 3 = 3 \bmod 3 = 0 $ . It can be shown that for greater $ m $ , the required condition will not be fulfilled.

In the third query of the first sample, $ 14 \bmod 4 = 2 \bmod 4 = 6 \bmod 4 = 2 $ . It can be shown that for greater $ m $ , the required condition will not be fulfilled.

## Limit



Time Limit
5.00s

Memory Limit
250.00MB

Tags: data structures, divide and conquer, math, number theory
Difficulty: 1700
# Three Strings

## Problem Description

You are given three strings: $ a $ , $ b $ , and $ c $ , consisting of lowercase Latin letters. The string $ c $ was obtained in the following way:

1. At each step, either string $ a $ or string $ b $ was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string $ c $ , until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of $ c $ .
2. Then, a certain number of characters in string $ c $ were randomly changed.

For example, from the strings $ a=\color{red}{\text{abra}} $ and $ b=\color{blue}{\text{cada}} $ , without character replacements, the strings $ \color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}} $ , $ \color{red}{\text{abra}}\color{blue}{\text{cada}} $ , $ \color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}} $ could be obtained.

Find the minimum number of characters that could have been changed in string $ c $ .

## Input Format

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

The first line of each test case contains one string of lowercase Latin letters $ a $ ( $ 1 \leq |a| \leq 10^3 $ ) — the first string, where $ |a| $ denotes the length of string $ a $ .

The second line of each test case contains one string of lowercase Latin letters $ b $ ( $ 1 \leq |b| \leq 10^3 $ ) — the second string, where $ |b| $ denotes the length of string $ b $ .

The third line of each test case contains one string of lowercase Latin letters $ c $ ( $ |c| = |a| + |b| $ ) — the third string.

It is guaranteed that the sum of $ |a| $ across all test cases does not exceed $ 2 \cdot 10^3 $ . Also, the sum of $ |b| $ across all test cases does not exceed $ 2 \cdot 10^3 $ .

## Output Format

For each test case, output a single integer — the minimum number of characters that could have been changed in string $ c $ .

## Sample #1

### Sample Input #1

```
7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg
```

### Sample Output #1

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

## Limit



Time Limit
2.50s

Memory Limit
250.00MB

Tags: dp, implementation, strings
Difficulty: 1500