Hakam Round #1
A. Stars and Bars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Suppose you want to count the number of ways to represent $$$n$$$ as the sum of $$$k$$$ positive integers. The stars and bars method gives a useful way to represent each such sum.

Write $$$n$$$ stars in a row and place $$$k-1$$$ bars in the gaps between them. The bars divide the stars into $$$k$$$ non-empty groups, and the size of each group is one of the positive integers in the sum.

For example, the string **|*|** represents the ordered tuple $$$(2, 1, 2)$$$, or the sum $$$2 + 1 + 2 = 5$$$. It has $$$5$$$ stars divided into $$$3$$$ non-empty groups, so it represents one way to write $$$5$$$ as a sum of $$$3$$$ positive integers.

Every different placement of the bars gives a different ordered tuple, and every ordered tuple of $$$k$$$ positive integers with sum $$$n$$$ corresponds to exactly one placement. Thus, counting these tuples is equivalent to choosing $$$k-1$$$ gaps for the bars among the $$$n-1$$$ gaps between consecutive stars. This gives $$$\binom{n-1}{k-1}$$$ possible tuples.

In this problem, you are given a valid stars-and-bars string. Write the sum represented by the string as an equation.

Input

The input consists of a string $$$s$$$ containing only the characters * and | ($$$1 \le |s| \le 1000$$$). The first and last characters of $$$s$$$ are guaranteed to be *, and no two bars are adjacent.

Output

Print the sizes of the groups of stars in order, separated by + , followed by = and the total number of stars.

Examples
Input
*|**|*
Output
1 + 2 + 1 = 4
Input
**|*|**
Output
2 + 1 + 2 = 5
B. Equal Substrings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting only of the characters A and B. In one move, you may swap two adjacent characters.

Find the minimum number of moves required to make the number of occurrences of the substring AB equal to the number of occurrences of the substring BA. If it is impossible, print $$$-1$$$.

Input

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

Each of the next $$$t$$$ lines contains a string $$$s$$$ consisting only of the characters A and B.

The length of each string does not exceed $$$300000$$$. The sum of the lengths of all strings does not exceed $$$300000$$$.

Output

For each test case, print the minimum number of adjacent swaps required, or $$$-1$$$ if it is impossible.

Example
Input
4
AAAA
AAABB
AAB
ABBA
Output
0
2
1
0
C. Non-decreasing Groups
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string of digits. Divide it into one or more non-empty groups of consecutive digits. Every digit must belong to exactly one group.

Read each group as an integer. The groups must be in non-decreasing order: the value of each group must be greater than or equal to the value of the group before it.

For example, the string 1234 can be divided as 1 | 2 | 34. The group values are $$$1$$$, $$$2$$$, and $$$34$$$, so they are in non-decreasing order. This division has $$$3$$$ groups. Your task is to find the largest number of groups possible.

Input

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

Each of the next $$$t$$$ lines contains a non-empty string $$$s$$$ consisting only of digits.

The length of each string does not exceed $$$300000$$$. The sum of the lengths of all strings does not exceed $$$300000$$$.

Output

For each test case, print the maximum number of groups.

Example
Input
4
1234
123
321
9000
Output
4
3
2
1
D. Remove Subs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$, of lengths $$$n$$$ and $$$m$$$.

You may remove one substring from $$$a$$$ and one subsequence from $$$b$$$. After these removals, the two arrays must be equal. Find the maximum possible length of the resulting arrays.

A substring is a group of consecutive elements of an array. A subsequence is formed by choosing some elements of an array without changing their order; the chosen elements do not have to be consecutive. When elements are removed, the remaining elements keep their original order.

Either removal may be empty, so you may leave either array unchanged. You may also remove an entire array. The answer can be $$$0$$$.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 200000$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n+m$$$).

The third line contains $$$m$$$ integers $$$b_1,b_2,\ldots,b_m$$$ ($$$1 \le b_i \le n+m$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$200000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$200000$$$.

Output

For each test case, print the maximum possible length of the two equal arrays after the removals.

Example
Input
4
5 3
1 2 3 4 5
1 3 5
3 3
1 2 1
1 2 1
2 2
1 2
3 4
4 3
2 1 2 3
1 2 3
Output
2
3
0
3
E. Suffix Stack
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. For each index $$$i$$$, perform the following process independently:

Start with an empty stack and read the elements $$$a_i,a_{i+1},\ldots,a_n$$$ from left to right. For each value $$$x$$$:

  • If the stack is not empty and its top value equals $$$x$$$, remove the top value. Do not push $$$x$$$ in this case.
  • Otherwise, push $$$x$$$ onto the stack.

For every $$$i$$$ from $$$1$$$ to $$$n$$$, find the size of the stack after processing all elements from $$$a_i$$$ to $$$a_n$$$.

Input

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

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

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

The sum of $$$n$$$ over all test cases does not exceed $$$100000$$$.

Output

For each test case, print $$$n$$$ integers. The $$$i$$$-th integer must be the size of the stack obtained by starting at index $$$i$$$.

Example
Input
3
5
1 2 2 1 3
4
1 2 1 2
6
1 2 2 3 3 1
Output
1 2 3 2 1
4 3 2 1
0 1 2 1 2 1
F. Count Subsequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$. Count the number of different non-empty subsequences of $$$a$$$ with length at most $$$k$$$.

A subsequence is obtained by removing zero or more elements from an array without changing the order of the remaining elements. Two subsequences are different if their lengths differ, or if their values differ at some position. Choosing different indices that give the same sequence of values counts only once.

For example, in the array $$$[1,2,1]$$$, choosing either occurrence of $$$1$$$ gives the same subsequence $$$[1]$$$. The different subsequences of length at most $$$2$$$ are $$$[1]$$$, $$$[2]$$$, $$$[1,2]$$$, $$$[1,1]$$$, and $$$[2,1]$$$, so the answer is $$$5$$$.

Since the answer can be large, print it modulo $$$1000000007$$$.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100000$$$, $$$1 \le k \le \min(n,100)$$$).

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

The sum of $$$n$$$ over all test cases does not exceed $$$100000$$$. There is no additional bound on the sum of $$$k$$$.

Output

For each test case, print the number of different non-empty subsequences of length at most $$$k$$$, modulo $$$1000000007$$$.

Example
Input
4
3 2
1 2 1
3 3
1 1 1
4 2
1 2 3 4
1 1
1
Output
5
3
10
1