2025-2026 ICPC, NERC, Southern and Volga Russian Regional Contest
A. Delete the Array
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer array of $$$n$$$ elements $$$a_1, a_2, \dots, a_n$$$. You can perform two types of operations on it:

  1. Delete the minimum element of the array; if there are several minimums, you can choose which one to delete.
  2. Delete the first two elements of the array if they are equal. This operation can be performed only if the array contains at least two elements.
The array shrinks after deletions. For example, if the array is $$$[5, 2, 5, 2, 2, 4]$$$ and you perform the first operation on the second element, it becomes $$$[5, 5, 2, 2, 4]$$$.

You can perform any operations any number of times and in any order. What is the minimum number of operations you need to make the array empty?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — 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 size of the array $$$a$$$.

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

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of operations to make the array $$$a$$$ empty using the operations above.

Example
Input
5
1
1
2
2 2
6
5 2 5 2 2 4
6
5 5 5 5 1 1
5
4 1 1 1 4
Output
1
1
4
3
4
Note

In the first test case, you can perform only the first operation once.

In the second test case, since the first two elements are equal, you can perform the second operation once and delete both elements.

In the third test case, it's optimal to perform the first operation and delete $$$a_2 = 2$$$. After that, you'll get the array $$$[5, 5, 2, 2, 4]$$$, and you can perform the second operation two times. In the result, you'll get the array $$$[4]$$$, so you need one more operation of the first type.

B. Convex Interval
time limit per test
3 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a list of $$$n$$$ pairwise distinct points $$$p_1, p_2, \dots, p_n$$$ on a 2D plane. An interval $$$[l, r]$$$ of points is called convex if the following conditions hold:

  • the length of the interval ($$$r - l + 1$$$) is at least $$$3$$$;
  • the points $$$p_l, p_{l+1}, \dots, p_r$$$ in this order form a strictly convex polygon written out in a clockwise order.

Recall that a strictly convex polygon is a convex polygon that has no three consecutive points on the same line.

Find the maximum length of a convex interval in the given list. If there are no convex intervals, print $$$0$$$.

Input

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$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of points.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of the point $$$p_i$$$.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$;
  • in each test case, the points are pairwise distinct (if $$$i \neq j$$$, either $$$x_i \neq x_j$$$ or $$$y_i \neq y_j$$$ holds).
Output

For each test case, print a single integer — the maximum length of a convex interval in the given list of points.

Example
Input
3
5
0 0
0 2
1 1
2 2
2 0
7
-4 5
-7 5
-4 8
-1 9
6 3
7 -5
4 4
6
-1 0
0 0
1 1
1 -1
0 1
1 0
Output
3
5
3

C. Monocarp, Polycarp and Brackets
time limit per test
3 с
memory limit per test
512 megabytes
input
standard input
output
standard output

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence an RBS.

Monocarp and Polycarp play a game. They have a string $$$s$$$ consisting of characters of two types: opening brackets and closing brackets. Monocarp also has a string $$$t$$$, which is initially empty.

The players take turns, Monocarp goes first. During Monocarp's turn, he has to choose either the first or the last character of the string $$$s$$$, remove it from $$$s$$$, and append it to the end of the string $$$t$$$. During Polycarp's turn, he has to choose either the first or the last character of the string $$$s$$$ and remove it.

If at any point in time, the string $$$t$$$ becomes a non-empty RBS, Monocarp wins. If the string $$$s$$$ becomes empty, and Monocarp has not won yet, Polycarp wins.

You have to determine which player wins if they play optimally.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 6000$$$) — the length of the string $$$s$$$.

The second line of each test case contains $$$s$$$ — a string consisting of $$$n$$$ characters. Each character of $$$s$$$ is either an opening bracket (ASCII code 40), or a closing bracket (ASCII code 41).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$6000$$$.

Output

For each test case, print Monocarp if Monocarp wins, or Polycarp if Polycarp wins.

Example
Input
6
4
(())
5
)((()
7
))))))(
6
()()()
6
((()()
6
()((()
Output
Monocarp
Polycarp
Monocarp
Monocarp
Polycarp
Monocarp
Note

In the first example, Monocarp can choose the leftmost character $$$s$$$ and append it to $$$t$$$. No matter what Polycarp does on his turn, the rightmost character of $$$s$$$ will be a closing bracket; so, Monocarp will be able to make $$$t$$$ an RBS by appending it to $$$t$$$ on the second turn.

In the second example, no matter which character Monocarp chooses on the first turn, the string $$$t$$$ will start with a closing bracket. So, it cannot become an RBS.

D. Gooseberry
time limit per test
5 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp really loves to eat gooseberry. The gooseberry season consists of $$$n$$$ days, and during each of these days, Monocarp can go to the market and buy a batch of gooseberries.

If Monocarp goes to the market during the day $$$i$$$, the batch he buys lasts for $$$a_i$$$ days (from day $$$i$$$ until the day $$$(i+a_i-1)$$$, inclusive), and during each of these days, he gets $$$b_i$$$ units of happiness from eating it. Monocarp won't go to the market until he has finished the current batch. In other words, the first day Monocarp can choose to go to the market again after buying the $$$i$$$-th batch is the day $$$(i + a_i)$$$. Monocarp does not have to go to the market every time he is out of gooseberry. However, he won't get any units of happiness during the days he does not have any gooseberries to eat.

Monocarp estimates the amount of joy he gets from the whole season as follows:

  • first, for every segment of consecutive $$$m$$$ days, he calculates $$$S_i$$$ — the total happiness he gets during those days. In other words, for every $$$i \in [1, n-m+1]$$$, $$$S_i = h_i + h_{i+1} + \dots + h_{i+m-1}$$$, where $$$h_i$$$ is the happiness Monocarp gets during the $$$i$$$-th day;
  • then, he takes the minimum value among $$$S_1, S_2, \dots, S_{n-m+1}$$$, which is the amount of joy he gets from the whole season.

Help Monocarp find a plan of purchasing gooseberry in such a way that the joy he gets from the whole season is the maximum possible!

Input

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 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le n$$$) — the number of days of the gooseberry season, and the length of each segment of days used in the calculations of joy, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$m \le a_i \le n$$$) — the number of days that the $$$i$$$-th batch of gooseberries lasts for. Note the unusual constraint.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the happiness Monocarp gets from this batch during each day.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two integers $$$p$$$ and $$$k$$$ in the first line, where $$$p$$$ is the maximum possible amount of joy Monocarp can get from the gooseberry season, and $$$k$$$ is the number of times Monocarp visits the market to buy a batch.

In the second line, print $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the days when Monocarp visits the market in increasing order.

If there are multiple optimal answers, output any of them.

Example
Input
10
2 1
1 1
4 7
3 2
2 2 3
2 5 3
4 3
3 4 3 3
9 8 13 4
4 2
4 2 2 3
1 10 7 3
5 4
4 4 5 5 5
7 2 1 7 3
7 3
3 4 4 6 5 3 3
9 3 3 2 4 8 9
8 3
4 3 4 6 3 6 6 4
7 9 2 7 2 4 8 9
9 4
4 9 4 8 9 6 8 8 5
9 4 7 4 2 5 8 7 6
10 3
3 5 6 7 3 4 5 8 10 4
1 5 4 2 1 3 1 2 4 3
12 2
4 2 2 3 2 4 4 4 4 3 3 3
7 1 9 8 6 4 5 9 8 9 1 2
Output
4 2
1 2 
5 1
2
22 2
1 4
10 1
2
24 2
1 5 
8 2
1 6 
8 2
2 7 
16 2
1 7 
4 2
3 10
6 4
1 5 8 12
Note

In the first test case, Monocarp can purchase gooseberry batches on both days. He is allowed to do that because the first batch lasts $$$1$$$ day, so he can buy the second batch on day $$$2$$$. Then $$$h = [4, 7]$$$. Since $$$m = 1$$$, $$$S_i$$$ is equal to $$$h_i$$$. Thus, the minimum in $$$S$$$ is $$$4$$$.

In the second test case, Monocarp can purchase a gooseberry batch on day $$$2$$$. $$$h = [0, 5, 5]$$$. Then $$$S_1 = h_1 + h_2 = 5$$$, $$$S_2 = h_2 + h_3 = 10$$$.

In the third test case, Monocarp can purchase gooseberry batches on days $$$1$$$ and $$$4$$$. $$$h = [9, 9, 9, 4]$$$. $$$S_1 = 27$$$, $$$S_2 = 22$$$. Note that Monocarp can't purchase batches on days $$$1$$$ and $$$3$$$, for example. The batch from day $$$1$$$ lasts until day $$$3$$$, so day $$$4$$$ is the earliest he can purchase another batch.

E. Limousine Rally
time limit per test
4 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You've got a new electronic handheld game "Limousine Rally", and you are so excited! In the game, you drive a car towards the finish while going around the obstacles. The road is represented by a grid $$$n$$$ rows long and $$$m$$$ columns wide. Each cell of the grid is either a normal part of the road or an obstacle.

The rows of the grid are numbered from $$$1$$$ to $$$n$$$ and the columns are numbered from $$$1$$$ to $$$m$$$. The cell in the $$$x$$$-th row and the $$$y$$$-th column is denoted $$$(x, y)$$$. The car has a length of $$$k$$$ cells and at the start of the game it occupies $$$k$$$ consecutive cells from $$$(1, 1)$$$ to $$$(k, 1)$$$.

The game is played in moves. Assuming that the car occupies cells from $$$(x, y)$$$ to $$$(x + k - 1, y)$$$ at the start of the move, you can perform one of the following actions:

  • if $$$y \gt 1$$$, shift the car left, so it will occupy cells from $$$(x, y - 1)$$$ to $$$(x + k - 1, y - 1)$$$;
  • if $$$y \lt m$$$, shift the car right, so it will occupy cells from $$$(x, y + 1)$$$ to $$$(x + k - 1, y + 1)$$$;
  • if $$$x + k - 1 \lt n$$$, advance the car forward, so it will occupy cells from $$$(x + 1, y)$$$ to $$$(x + k, y)$$$.

A move is valid only if none of the cells the car is going to occupy contains an obstacle. The car can not rotate, i. e. it is always aligned vertically. The cells initially occupied by the car do not contain obstacles.

What is the maximum row the car can reach from the starting position using only valid moves? A row is reached if a cell of the car is located in that row. There is no limit on the number of moves.

Input

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 10^6$$$; $$$1 \le n \cdot m \le 10^6$$$; $$$1 \le k \le n$$$) — the number of rows and columns in the grid, and the length of the car.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ characters '.' and/or 'x' — the description of the $$$i$$$-th row. A '.' denotes a normal part of the road, and an 'x' denotes an obstacle.

Additional constraint of the input: the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the maximum row the car can reach.

Example
Input
3
3 2 2
..
..
xx
4 5 2
.x...
.....
...x.
xxxx.
5 4 1
.x.x
....
xxx.
....
.xxx
Output
2
3
5

F. Jenga
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Jenga is a game played by two or more players. They start with a tower of $$$n$$$ rows, each row consists of $$$3$$$ rectangular blocks. Then they remove blocks one by one until the tower falls. The player which breaks the tower loses. Removed blocks are usually placed on top of the tower forming the new row; however, in this problem, we'll consider a modified version of the game: removed blocks are put aside and are never returned to the tower.

Monocarp and Polycarp play Jenga a lot. They noticed that a tower row remains stable if it contains either the two side blocks, or the central block. Of course, if there are any additional blocks in the row, it is also stable. Thus, rows xxx, x.x, xx., .xx, .x. are stable, while rows x.., ..x and ... are unstable. Here and further on, the character 'x' depicts a block which is not removed yet, and '.' represents an empty space after removing a block. If at least one row (even the topmost one) in the tower becomes unstable, the tower immediately falls.

Currently, Monocarp and Polycarp have a tower of $$$n$$$ rows, where some blocks may already be removed (but each row is stable). It is Monocarp's turn now. Given the state of the tower (which blocks are removed and which are still present), you have to determine who wins, assuming both players play optimally.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — the number of rows in the tower.

Then, $$$n$$$ lines follow, the $$$i$$$-th of them contains $$$6$$$ characters in the format ***=== or ===***, where each '*' is either 'x' or '.' — the state of the $$$i$$$-th row from the top. Rows ***=== and ===*** alternate, describing the Jenga tower.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$, and each row of the tower is stable.

Output

For each test case, print Monocarp if Monocarp wins; otherwise, print Polycarp.

Example
Input
4
4
xx.===
===x.x
.xx===
===xxx
2
===x.x
.x.===
3
===xxx
xxx===
===xxx
10
===xxx
x.x===
===xxx
.xx===
===xxx
xx.===
===xxx
x.x===
===xxx
xxx===
Output
Monocarp
Polycarp
Monocarp
Polycarp
Note

In the first test case, Monocarp should remove the central block from the bottom row. After this, it is possible to remove only two blocks from the Jenga tower: the first block from the first row and the third block from the third row. If any other block is removed, the tower falls. Whatever block Polycarp removes, Monocarp takes the other one, leaving Polycarp with no choice.

In the second test case, no blocks can be removed without breaking Jenga. So, Polycarp wins.

In the third test case, Monocarp has a winning strategy.

The fourth test case represents the configuration shown in the picture.

G. String Transformation
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$, consisting of lowercase Latin letters.

You can perform the following operation:

  • choose indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le |s|$$$) and a character $$$c$$$ (any lowercase Latin letter), then remove all occurrences of $$$c$$$ from the $$$l$$$-th to the $$$r$$$-th index, inclusive.

For example, if $$$s$$$ is abaabc, you can transform it into babc (by using $$$l=1$$$, $$$r=3$$$, $$$c =$$$ 'a'), abaac (by using $$$l=4$$$, $$$r=6$$$, $$$c =$$$ 'b') and abaabc (by using $$$l=2$$$, $$$r=5$$$, $$$c =$$$ 'c').

Your task is to calculate the number of different strings that can be obtained using the aforementioned operation exactly once.

Input

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

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of lowercase Latin letters.

Additional constraint on the input: the sum of $$$|s|$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of different strings that can be obtained using the aforementioned operation exactly once.

Example
Input
4
abaabc
qf
x
icpc
Output
10
3
2
6
Note

All the possible strings that can be obtained in the first example:

  • abaabc (by choosing $$$l = 1$$$, $$$r=6$$$, $$$c =$$$ 'd');
  • abaab (by choosing $$$l = 2$$$, $$$r=6$$$, $$$c =$$$ 'c');
  • abaac (by choosing $$$l = 4$$$, $$$r=6$$$, $$$c =$$$ 'b');
  • ababc (by choosing $$$l = 4$$$, $$$r=6$$$, $$$c =$$$ 'a');
  • aaabc (by choosing $$$l = 1$$$, $$$r=3$$$, $$$c =$$$ 'b');
  • baabc (by choosing $$$l = 1$$$, $$$r=2$$$, $$$c =$$$ 'a');
  • aaac (by choosing $$$l = 1$$$, $$$r=6$$$, $$$c =$$$ 'b');
  • abbc (by choosing $$$l = 3$$$, $$$r=4$$$, $$$c =$$$ 'a');
  • babc (by choosing $$$l = 1$$$, $$$r=3$$$, $$$c =$$$ 'a');
  • bbc (by choosing $$$l = 1$$$, $$$r=5$$$, $$$c =$$$ 'a').

H. Rigged Matchmaking
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

The World Table Tennis Championship is approaching! This year, a serious competition is expected between two countries: Monland and Berland. Each country is represented by its national team.

Thanks to his high abilities (not only in tennis), Monocarp has made it to the Monland team. By studying and analyzing the previous performances of all team members, Monocarp was able to determine their skills. It turned out that Monland is represented by $$$(r_M - l_M + 1)$$$ athletes with skills $$$l_M$$$, $$$l_M + 1$$$, $$$l_M + 2$$$, and so on, up to $$$r_M$$$ inclusive. Similarly, Berland is represented by athletes with skills $$$l_B$$$, $$$l_B + 1$$$, ..., $$$r_B$$$. Unfortunately for Monocarp, he turned out to be that athlete with skill $$$l_M$$$.

The table tennis championship is organized in a very complicated way, but it will begin with a qualifying round. This round consists of a series of two-on-two games: two representatives from Monland play against two athletes from Berland.

To Monocarp's great joy, the selection of athletes for the games is done by an electronic system. Since Monocarp is also a fairly strong programmer, he managed (not without effort) to hack this system and can now control the team compositions for the games.

His plan is to manipulate the matches he participates in and ensure his victories in them. Monocarp believes that he and his partner will be able to defeat an opposing team if the total skill of his team is higher than or equal to the total skill of their two opponents.

However, Monocarp decided that it would be safer if none of the athletes he plays with or against are repeated. Thus, Monocarp wants to arrange the games so that no athlete from Berland plays against Monocarp more than once, and no athlete from Monland plays with him more than once.

Help Monocarp determine the maximum number of winning games he can arrange in this way.

Input

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

The first line of each test case contains two integers $$$l_M$$$ and $$$r_M$$$ ($$$1 \le l_M \lt r_M \le 10^9$$$) — the skill levels of Monland's team. Monocarp is the one who has skill $$$l_M$$$.

The second line of each test case contains two integers $$$l_B$$$ and $$$r_B$$$ ($$$1 \le l_B \lt r_B \le 10^9$$$) — the skill levels of Berland's team.

Output

For each test case, print one integer — the maximum number of wins Monocarp can achieve.

Example
Input
3
10 13
11 15
2000 3000
1 2000
42 200
1 400
Output
1
1000
96
Note

In the first test case, even if Monocarp (skill $$$10$$$) joined forces with the strongest athlete in his team (the one with skill $$$13$$$), they can only win against a team consisting of the two weakest athletes of the Berland's team (athletes with skills $$$11$$$ and $$$12$$$), since $$$10 + 13 \ge 11 + 12$$$.

In the second test case, it doesn't matter who Monocarp will play with and against, since any Monocarp's team will have total skill higher than $$$4000$$$ while any Berland team skill is lower than $$$4000$$$.

I. Remove Colors
time limit per test
5 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree, consisting of $$$n$$$ vertices. Every vertex has a color: vertex $$$i$$$ is colored $$$a_i$$$.

In one operation, you can choose some colors (possibly, just one or all of them) and remove all vertices of all chosen colors. The edges incident to at least one removed vertex also get removed. The cost of the operation is $$$k \cdot c$$$, where $$$k$$$ is the number of chosen colors and $$$c$$$ is the number of removed vertices.

The operation can only be applied if the following condition holds: after the operation, no two vertices of the same color belong to different connected components.

What's the minimum total cost of operations required to remove the entire tree?

Input

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$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — the number of vertices of the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the colors of the vertices.

Each of the next $$$n - 1$$$ lines contain two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the edges of the tree.

Additional constraints on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$, the given edges form a valid tree.

Output

For each test case, print a single integer — the minimum total cost of operations required to remove the entire tree.

Example
Input
4
3
1 1 2
1 2
2 3
3
3 1 2
1 3
3 2
4
1 2 1 2
1 2
2 3
3 4
10
4 5 1 3 5 2 3 3 1 4
5 1
2 10
3 7
6 8
9 8
9 5
5 7
4 6
10 5
Output
3
3
8
19

J. Shift the Number
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp invented a new operation on integers: $$$n \rightarrow x$$$, which he calls a cyclic shift. The operation is defined only for positive integers $$$n$$$ that do not contain zeros in their decimal representation, and for positive integers $$$x$$$. It is defined as follows: let the decimal representation of $$$n$$$ be $$$\overline{n_1 n_2 \dots n_{m-1} n_m}$$$, then:

$$$$$$n \rightarrow x = \begin{cases} \overline{n_m n_1 n_2 \dots n_{m - 1}}, & \text{if } x = 1 \\ (n \rightarrow (x - 1)) \rightarrow 1, & \text{otherwise} \end{cases} $$$$$$

In other words, $$$n \rightarrow x$$$ is the integer you get if you perform the following operation $$$x$$$ times: move the rightmost digit in the decimal representation of $$$n$$$ to the leftmost position, shifting all other digits one position to the right.

For example, $$$123 \rightarrow 1 = 312$$$, $$$123 \rightarrow 2 = 231$$$, $$$123 \rightarrow 9 = 123$$$, $$$1 \rightarrow 1 = 1$$$.

Monocarp is interested in how similar this operation is to addition. Given an integer $$$n$$$, he wants to find all values of $$$x$$$ such that $$$n \rightarrow x = n + x$$$.

Input

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

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \lt 10^9$$$).

Additional constraint on the input: all digits in the decimal representation of $$$n$$$ are not equal to $$$0$$$.

Output

For each test case, print the number of suitable values of $$$x$$$. Then, print these values of $$$x$$$ in increasing order.

Example
Input
7
12
34
228
1113
1114
12345678
123456789
Output
1
9
1
9
0

1
198
2
27 2997
7
11111103 22222134 33332445 44435556 55466667 65777778 68888889
0

K. Strange Array
time limit per test
5 с
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given three integers $$$n$$$, $$$k$$$ and $$$m$$$. Additionally, you have $$$m$$$ integer triples ($$$l_i, r_i, x_i$$$).

Let's define the value of an integer array $$$a$$$ as follows:

  • let $$$A$$$ be the bitwise OR of all elements of the array;
  • let $$$y_i$$$ be the bitwise XOR of $$$a[l_i], a[l_i+1], \dots, a[r_i]$$$;
  • let $$$z_i$$$ be the bitwise AND of $$$y_i$$$ and $$$x_i$$$;
  • the value of the array is $$$k \cdot A - \sum \limits_{i=1}^{m} z_i$$$.
Your task is to find an array $$$a$$$ consisting of $$$n$$$ integers from $$$0$$$ to $$$2^{30} - 1$$$ with the maximum value.
Input

The first line contains three integers $$$n, k$$$ and $$$m$$$ ($$$1 \le n, k \le 100$$$; $$$0 \le m \le 5000$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains three integers $$$l_i, r_i$$$ and $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$; $$$0 \le x \lt 2^{30}$$$).

Output

Print $$$n$$$ integers — the array consisting of $$$n$$$ integers from $$$0$$$ to $$$2^{30} - 1$$$ with the maximum value.

Examples
Input
3 2 4
3 3 1
1 2 3
1 1 1
1 3 3
Output
3 3 1073741820 
Input
2 2 0
Output
0 1073741823 

L. Red and Blue Edges
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an undirected graph of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially, there are no edges.

You should process $$$q$$$ queries. There are two types of queries:

  • $$$1~u~v$$$ — a red edge is added between vertices $$$u$$$ and $$$v$$$;
  • $$$2~u~v$$$ — a blue edge is added between vertices $$$u$$$ and $$$v$$$.

Note that the graph might contain multiple edges and/or self-loops.

After each query, find the maximum number of edges that can be deleted from the graph if the following conditions are satisfied:

  • The number of deleted red edges is equal to the number of deleted blue edges;
  • The graph connectivity isn't changed. In other words, for every pair of vertices ($$$u, v$$$), if there was a path between $$$u$$$ and $$$v$$$ before the deletion, there should still be a path between them after the deletion. Note the colors of the edges in the path don't matter.

Note that you don't actually delete the edges from the graph, you only calculate the maximum number of edges you can delete.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of vertices in the graph and the number of queries.

Each of the next $$$q$$$ lines contains three integers $$$t, u, v$$$ ($$$1 \le t \le 2$$$; $$$1 \le u, v \le n$$$) — the description of the query.

Output

After each query, print one integer — the maximum number of edges you can delete from the graph.

Examples
Input
4 5
1 3 3
2 4 4
1 1 2
2 1 2
1 1 2
Output
0
2
2
2
4
Input
5 9
2 2 5
1 4 1
1 5 3
2 5 1
1 1 3
2 3 2
1 4 2
2 4 4
1 3 5
Output
0
0
0
0
0
2
2
4
4

M. Tactical Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp plays a computer game — a tactical RPG, to be specific. Right now, he has to defeat several enemies to win the current battle.

The enemy side of the battlefield can be represented as a row of $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$ from left to right. Every cell is either empty (represented by the character '0'), or contains an enemy (represented by the character '1').

To win the battle, Monocarp can perform the following actions:

  • choose an enemy which is not eliminated yet and cast a lightning bolt at that enemy, instantly eliminating them;
  • choose an enemy which is not eliminated yet and launch a fireball at that enemy. The fireball's explosion eliminates both the target and the adjacent enemies (if there are any). Formally, if the fireball is launched at the enemy in the cell $$$i$$$, the enemies in the cells $$$(i-1)$$$ and $$$(i+1)$$$, if they exist, are also eliminated. Note that a fireball can be launched only at an enemy; Monocarp cannot launch a fireball at an empty cell.

Of course, fireballs are more efficient; however, Monocarp can launch at most one fireball during the battle. Thankfully, he can cast the lightning bolt any number of times.

Your task is to help Monocarp determine the minimum number of actions he has to perform in order to eliminate all enemies.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of cells.

The second line of each test case contains one string $$$s$$$ ($$$|s| = n$$$). Each character of $$$s$$$ is either '0' (if the corresponding cell is empty) or '1' (if the corresponding cell contains an enemy).

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

Output

For each test case, print one integer — the minimum number of actions Monocarp has to perform in order to eliminate all enemies.

Example
Input
4
5
00000
7
1010101
8
01110110
9
110101100
Output
0
4
3
4