yl-9/probench huggingface dataset:
# Digital string maximization

## Problem Description

You are given a string $ s $ , consisting of digits from $ 0 $ to $ 9 $ . In one operation, you can pick any digit in this string, except for $ 0 $ or the leftmost digit, decrease it by $ 1 $ , and then swap it with the digit left to the picked.

For example, in one operation from the string $ 1023 $ , you can get $ 1103 $ or $ 1022 $ .

Find the lexicographically maximum string you can obtain after any number of operations.

## Input Format

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

Each test case consists of a single line consisting of a digital string $ s $ ( $ 1 \le |s| \le 2\cdot 10^5 $ ), where $ |s| $ denotes the length of $ s $ . The string does not contain leading zeroes.

It is guaranteed that the sum of $ |s| $ of all test cases doesn't exceed $ 2\cdot 10^5 $ .

## Output Format

For each test case, print the answer on a separate line.

## Sample #1

### Sample Input #1

```
6
19
1709
11555
51476
9876543210
5891917899
```

### Sample Output #1

```
81
6710
33311
55431
9876543210
7875567711
```

## Hint

In the first example, the following sequence of operations is suitable: $ 19 \rightarrow 81 $ .

In the second example, the following sequence of operations is suitable: $ 1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710 $ .

In the fourth example, the following sequence of operations is suitable: $ 51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, greedy, math, strings
Difficulty: 1300
# Uninteresting Number

## Problem Description

You are given a number $ n $ with a length of no more than $ 10^5 $ .

You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit $ x $ , then the value of $ x^2 $ must be less than $ 10 $ ).

Is it possible to obtain a number that is divisible by $ 9 $ through these operations?

## Input Format

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

The only line of each test case contains the number $ n $ , without leading zeros. The length of the number does not exceed $ 10^5 $ .

It is guaranteed that the sum of the lengths of the numbers across all test cases does not exceed $ 10^5 $ .

## Output Format

For each test case, output "YES" if it is possible to obtain a number divisible by $ 9 $ using the described operations, 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

```
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632
```

### Sample Output #1

```
NO
YES
YES
NO
NO
YES
NO
YES
YES
```

## Hint

In the first example, from the integer $ 123 $ , it is possible to obtain only $ 123 $ , $ 143 $ , $ 129 $ , and $ 149 $ , none of which are divisible by $ 9 $ .

In the second example, you need to replace the second digit with its square; then $ n $ will equal $ 342 = 38 \cdot 9 $ .

In the third example, the integer is already divisible by $ 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, dp, math
Difficulty: 1200
# Transfusion

## Problem Description

You are given an array $ a $ of length $ n $ . In one operation, you can pick an index $ i $ from $ 2 $ to $ n-1 $ inclusive, and do one of the following actions:

- Decrease $ a_{i-1} $ by $ 1 $ , then increase $ a_{i+1} $ by $ 1 $ .
- Decrease $ a_{i+1} $ by $ 1 $ , then increase $ a_{i-1} $ by $ 1 $ .

After each operation, all the values must be non-negative. Can you make all the elements equal after any number of operations?

## Input Format

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

First line of each test case consists of one integer $ n $ ( $ 3 \le n \le 2\cdot 10^5 $ ).

Second line of each test case consists of $ n $ integers $ a_i $ ( $ 1 \le a_i \le 10^9 $ ).

It is guaranteed that the sum of $ n $ of all test cases doesn't exceed $ 2\cdot 10^5 $ .

## Output Format

For each test case, print "YES" without quotation marks if it is possible to make all the elements equal after any number of operations; otherwise, print "NO" without quotation marks.

You can print answers in any register: "yes", "YeS", "nO" — will also be considered correct.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
YES
NO
YES
NO
YES
NO
NO
NO
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, greedy, math
Difficulty: 1100
# Line Breaks

## Problem Description

Kostya has a text $ s $ consisting of $ n $ words made up of Latin alphabet letters. He also has two strips on which he must write the text. The first strip can hold $ m $ characters, while the second can hold as many as needed.

Kostya must choose a number $ x $ and write the first $ x $ words from $ s $ on the first strip, while all the remaining words are written on the second strip. To save space, the words are written without gaps, but each word must be entirely on one strip.

Since space on the second strip is very valuable, Kostya asks you to choose the maximum possible number $ x $ such that all words $ s_1, s_2, \dots, s_x $ fit on the first strip of length $ m $ .

## Input Format

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

The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 50 $ ; $ 1 \le m \le 500 $ ) — the number of words in the list and the maximum number of characters that can be on the first strip.

The next $ n $ lines contain one word $ s_i $ of lowercase Latin letters, where the length of $ s_i $ does not exceed $ 10 $ .

## Output Format

For each test case, output the maximum number of words $ x $ such that the first $ x $ words have a total length of no more than $ m $ .

## Sample #1

### Sample Input #1

```
5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
codeforces
3 2
ab
c
d
3 2
abc
ab
a
```

### Sample Output #1

```
1
2
2
1
0
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation
Difficulty: 800
# MEX OR Mania

## Problem Description

An integer sequence $ b_1, b_2, \ldots, b_n $ is good if $ \operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1 $ . Here, $ \operatorname{mex(c)} $ denotes the MEX $ ^{\text{∗}} $ of the collection $ c $ , and $ | $ is the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) operator.

Shohag has an integer sequence $ a_1, a_2, \ldots, a_n $ . He will perform the following $ q $ updates on $ a $ :

- $ i $ $ x $ — increase $ a_i $ by $ x $ .

After each update, help him find the length of the longest good subarray $ ^{\text{†}} $ of $ a $ .

 $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ c_1, c_2, \ldots, c_k $ is defined as the smallest non-negative integer $ y $ which does not occur in the collection $ c $ .

 $ ^{\text{†}} $ An array $ d $ is a subarray of an array $ f $ if $ d $ can be obtained from $ f $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format

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

The first line of each test case contains two space-separated integers $ n $ and $ q $ ( $ 1 \le n, q \le 10^5 $ ).

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ).

The next $ q $ lines of each test case are of the following form:

- $ i $ $ x $ ( $ 1 \le i, x \le n $ ) — it means you should increase $ a_i $ by $ x $ .

It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 10^5 $ and the sum of $ q $ doesn't exceed $ 10^5 $ .

## Output Format

For each test case, output $ q $ lines — on the $ i $ -th line output the length of the longest good subarray of $ a $ after the $ i $ -th update.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
6
3
2
0
```

## Hint

In the first test case, after the first update, the array becomes $ [0, 0, 1, 0, 1, 1] $ , and here the whole array is good because $ \operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1 $ .

After the second update, the array becomes $ [0, 0, 3, 0, 1, 1] $ , and here the subarray $ [0, 1, 1] $ has the maximum length among all the good subarrays.

Finally, after the third update, the array becomes $ [0, 0, 3, 0, 1, 4] $ , and here the subarrays $ [0, 0] $ and $ [0, 1] $ both have the maximum length among all the good subarrays.

## Limit



Time Limit
4.00s

Memory Limit
1000.00MB

Tags: bitmasks, brute force, data structures, dsu, implementation
Difficulty: 2700
# MEX Cycle

## Problem Description

Evirir the dragon has many friends. They have 3 friends! That is one more than the average dragon.

You are given integers $ n $ , $ x $ , and $ y $ . There are $ n $ dragons sitting in a circle. The dragons are numbered $ 1, 2, \ldots, n $ . For each $ i $ ( $ 1 \le i \le n $ ), dragon $ i $ is friends with dragon $ i - 1 $ and $ i + 1 $ , where dragon $ 0 $ is defined to be dragon $ n $ and dragon $ n + 1 $ is defined to be dragon $ 1 $ . Additionally, dragons $ x $ and $ y $ are friends with each other (if they are already friends, this changes nothing). Note that all friendships are mutual.

Output $ n $ non-negative integers $ a_1, a_2, \ldots, a_n $ such that for each dragon $ i $ ( $ 1 \le i \le n $ ), the following holds:

- Let $ f_1, f_2, \ldots, f_k $ be the friends of dragon $ i $ . Then $ a_i = \operatorname{mex}(a_{f_1}, a_{f_2}, \ldots, a_{f_k}) $ . $ ^{\text{∗}} $

 $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ c_1, c_2, \ldots, c_m $ is defined as the smallest non-negative integer $ t $ which does not occur in the collection $ c $ .

## Input Format

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

The first and only line of each test case contains three integers $ n $ , $ x $ , $ y $ ( $ 3 \le n \le 2 \cdot 10^5 $ , $ 1 \le x < y \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 $ n $ space-separated non-negative integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) on a line that satisfy the condition in the statement. If there are multiple solutions, print any of them. It can be proven that under the problem constraints, a solution with $ 0 \le a_i \le 10^9 $ always exists.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

For the first test case:

- $ i = 1 $ : Dragon $ 1 $ 's friends are dragons $ 2, 3, 5 $ . $ \operatorname{mex}(a_2, a_3, a_5) = \operatorname{mex}(2, 1, 1) = 0 = a_1 $ , so the condition for dragon $ 1 $ is satisfied.
- $ i = 2 $ : Dragon $ 2 $ 's friends are dragons $ 1, 3 $ . $ \operatorname{mex}(a_1, a_3) = \operatorname{mex}(0, 1) = 2 = a_2 $ .
- $ i = 3 $ : Dragon $ 3 $ 's friends are dragons $ 1, 2, 4 $ . $ \operatorname{mex}(a_1, a_2, a_4) = \operatorname{mex}(0, 2, 0) = 1 = a_3 $ .
- $ i = 4 $ : Dragon $ 4 $ 's friends are dragons $ 3, 5 $ . $ \operatorname{mex}(a_3, a_5) = \operatorname{mex}(1, 1) = 0 = a_4 $ .
- $ i = 5 $ : Dragon $ 5 $ 's friends are dragons $ 1, 4 $ . $ \operatorname{mex}(a_1, a_4) = \operatorname{mex}(0, 0) = 1 = a_5 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, greedy, implementation
Difficulty: 1500
# pspspsps

## Problem Description

Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...

Given a string $ s = s_1s_2\ldots s_n $ of length $ n $ consisting of characters p, s, and . (dot), determine whether a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ exists, such that for all integers $ i $ ( $ 1 \le i \le n $ ):

- If $ s_i $ is p, then $ [p_1, p_2, \ldots, p_i] $ forms a permutation (of length $ i $ );
- If $ s_i $ is s, then $ [p_i, p_{i+1}, \ldots, p_{n}] $ forms a permutation (of length $ n-i+1 $ );
- If $ s_i $ is ., then there is no additional restriction.

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

## Input Format

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

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 500 $ ), the length of $ s $ .

The second line of each test case contains a string $ s $ of length $ n $ that consists of the characters p, s, and ..

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

## Output Format

For each test case, output YES or NO on a line. Output YES if there is such a permutation and NO otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
9
4
s.sp
6
pss..s
5
ppppp
2
sp
4
.sp.
8
psss....
1
.
8
pspspsps
20
....................
```

### Sample Output #1

```
YES
NO
YES
YES
NO
NO
YES
NO
YES
```

## Hint

For the first test case, one permutation that works is $ p = [3, 4, 1, 2] $ . The restrictions are as follows:

- $ s_1 = $ s: $ [p_1, p_2, p_3, p_4] = [3, 4, 1, 2] $ forms a permutation.
- $ s_2 = $ .: No additional restriction.
- $ s_3 = $ s: $ [p_3, p_4] = [1, 2] $ forms a permutation.
- $ s_4 = $ p: $ [p_1, p_2, p_3, p_4] = [3, 4, 1, 2] $ forms a permutation.

For the second test case, it can be proven that there is no permutation that satisfies all restrictions.

For the third test case, one permutation that satisfies the constraints is $ p = [1, 2, 3, 4, 5] $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, graph matchings, implementation
Difficulty: 1300
# MEX Destruction

## Problem Description

Evirir the dragon snuck into a wizard's castle and found a mysterious contraption, and their playful instincts caused them to play with (destroy) it...

Evirir the dragon found an array $ a_1, a_2, \ldots, a_n $ of $ n $ non-negative integers.

In one operation, they can choose a non-empty subarray $ ^{\text{∗}} $ $ b $ of $ a $ and replace it with the integer $ \operatorname{mex}(b) $ $ ^{\text{†}} $ . They want to use this operation any number of times to make $ a $ only contain zeros. It can be proven that this is always possible under the problem constraints.

What is the minimum number of operations needed?

 $ ^{\text{∗}} $ An array $ c $ is a subarray of an array $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

 $ ^{\text{†}} $ The minimum excluded (MEX) of a collection of integers $ f_1, f_2, \ldots, f_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ f $ .

## Input Format

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

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

The second line of each test case contains $ n $ space-separated integers, $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 100 $ ).

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

## Output Format

For each test case, output a single integer on a line, the minimum number of operations needed to make $ a $ contain only zeros.

## Sample #1

### Sample Input #1

```
10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1
```

### Sample Output #1

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

## Hint

In the first test case, Evirir can choose the subarray $ b = [1, 2, 3] $ and replace it with $ \operatorname{mex}(1, 2, 3) = 0 $ , changing $ a $ from $ [0, \underline{1, 2, 3}] $ to $ [0, 0] $ (where the chosen subarray is underlined). Therefore, the answer is $ 1 $ .

In the second test case, $ a $ already contains only $ 0 $ s, so no operation is needed.

In the third test case, Evirir can change $ a $ as follows: $ [1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0] $ . Here, $ \operatorname{mex}(0, 1, 0, 1) = 2 $ and $ \operatorname{mex}(1, 2) = 0 $ .

In the fourth test case, Evirir can choose $ b $ to be the entire array $ a $ , changing $ a $ from $ [\underline{3, 1, 4, 1, 5}] $ to $ [0] $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Kevin and Puzzle (Hard Version)

## Problem Description

This is the hard version of the problem. The difference between the versions is that in this version, you need to count the number of good arrays. You can hack only if you solved all versions of this problem.

Kevin is visiting the Red Church, and he found a puzzle on the wall.

For an array $  a  $ , let $  c(l,r)  $ indicate how many distinct numbers are among $  a_l, a_{l+1}, \ldots, a_r  $ . In particular, if $  l > r  $ , define $  c(l,r) = 0  $ .

You are given a string $  s  $ of length $  n  $ consisting of letters $  \texttt{L}  $ and $  \texttt{R}  $ only. Let a non-negative array $  a  $ be called good, if the following conditions hold for $  1 \leq i \leq n  $ :

- if $ s_i=\verb!L! $ , then $ c(1,i-1)=a_i $ ;
- if $ s_i=\verb!R! $ , then $ c(i+1,n)=a_i $ .

You need to count the number of good arrays $ a $ . Since the answer may be large, you only need to output the answer modulo $ 998\,244\,353 $ .

## Input Format

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

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

The second line of each test case contains a string $ s $ with a length $ n $ , containing only English uppercase letters $ \verb!L! $ and $ \verb!R! $ .

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 number of good arrays modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
4
3
LLR
3
RRL
4
RRLR
5
LLRLR
```

### Sample Output #1

```
1
2
0
1
```

## Hint

All arrays satisfying the conditions can be found in the easy version of this problem.

## Limit



Time Limit
6.00s

Memory Limit
500.00MB

Tags: bitmasks, fft, math
Difficulty: 3500
# Kevin and Puzzle (Easy Version)

## Problem Description

This is the easy version of the problem. The difference between the versions is that in this version, you need to find any one good array. You can hack only if you solved all versions of this problem.

Kevin is visiting the Red Church, and he found a puzzle on the wall.

For an array $  a  $ , let $  c(l,r)  $ indicate how many distinct numbers are among $  a_l, a_{l+1}, \ldots, a_r  $ . In particular, if $  l > r  $ , define $  c(l,r) = 0  $ .

You are given a string $  s  $ of length $  n  $ consisting of letters $  \texttt{L}  $ and $  \texttt{R}  $ only. Let a non-negative array $  a  $ be called good, if the following conditions hold for $  1 \leq i \leq n  $ :

- if $ s_i=\verb!L! $ , then $ c(1,i-1)=a_i $ ;
- if $ s_i=\verb!R! $ , then $ c(i+1,n)=a_i $ .

If there is a good array $ a $ , print any of the good arrays. Otherwise, report that no such arrays exists.

## Input Format

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

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

The second line of each test case contains a string $ s $ with a length $ n $ , containing only English uppercase letters $ \verb!L! $ and $ \verb!R! $ .

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, if a good array exists, print $ n $ non-negative integers: a good array $ a $ . Otherwise, print a single integer $ -1 $ .

If there are multiple arrays $ a $ satisfying the conditions, you can output any of them.

## Sample #1

### Sample Input #1

```
4
3
LLR
3
RRL
4
RRLR
5
LLRLR
```

### Sample Output #1

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

## Hint

In the first test case, the array $ [0,1,0] $ satisfies the conditions because:

- When $ i=1 $ , $ s_i=\verb!L! $ , and $ c(1,0)=0 $ ;
- When $ i=2 $ , $ s_i=\verb!L! $ , and $ c(1,1)=1 $ , since there is only one distinct number in $ a_1 $ ;
- When $ i=3 $ , $ s_i=\verb!R! $ , and $ c(4,3)=0 $ .

In the second test case, another suitable answer is $ [1,1,1] $ .

In the third test case, it can be proven that there's no array satisfying the conditions.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: constructive algorithms
Difficulty: 3500
# Kevin and Strange Operation

## Problem Description

Kevin is exploring problems related to binary strings in Chinatown. When he was at a loss, a stranger approached him and introduced a peculiar operation:

- Suppose the current binary string is $  t  $ , with a length of $  \vert t \vert  $ . Choose an integer $  1 \leq p \leq \vert t \vert  $ . For all $  1 \leq i < p  $ , simultaneously perform the operation $  t_i = \max(t_i, t_{i+1})  $ , and then delete $  t_p  $ .

For example, suppose the current binary string is 01001, and you choose $  p = 4  $ . Perform $  t_i = \max(t_i, t_{i+1})  $ for $ t_1 $ , $ t_2 $ , and $  t_3  $ , transforming the string into 11001, then delete $  t_4  $ , resulting in 1101.

Kevin finds this strange operation quite interesting. Thus, he wants to ask you: Given a binary string $  s  $ , how many distinct non-empty binary strings can you obtain through any number of operations (possibly zero)?

Since the answer may be very large, you only need to output the result modulo $ 998\,244\,353 $ .

## Input Format

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

For each test case, the only line contains a binary string $  s  $ ( $  1 \le \lvert s \rvert \le 10^6  $ ).

It is guaranteed that the sum of $ \lvert s \rvert $ over all test cases does not exceed $ 10^6 $ .

## Output Format

For each test case, print a single integer in the only line of the output — the number of distinct non-empty binary strings you can obtain, modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
2
11001
000110111001100
```

### Sample Output #1

```
9
73
```

## Hint

In the first test case, all the binary strings you can obtain are: 11001, 1001, 1101, 001, 101, 111, 01, 11, and 1. There are $  9  $ in total.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dp
Difficulty: 3100