vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp has just finished writing down the lecture on elvish languages. The language this week was "VwV" (pronounced as "uwu"). The writing system of this language consists of only two lowercase Latin letters: 'v' and 'w'.

Unfortunately, Polycarp has written all the lecture in cursive and without any spaces, so the notes look like a neverending sequence of squiggles. To be exact, Polycarp can't tell 'w' apart from 'vv' in his notes as both of them consist of the same two squiggles.

Luckily, his brother Monocarp has better writing habits, so Polycarp managed to take his notes and now wants to make his own notes more readable. To do that he can follow the notes of Monocarp and underline some letters in his own notes in such a way that there is no more ambiguity. If he underlines a 'v', then it can't be mistaken for a part of some 'w', and if the underlines a 'w', then it can't be mistaken for two adjacent letters 'v'.

What is the minimum number of letters Polycarp should underline to make his notes unambiguous?

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of testcases.

Each of the next t lines contains a non-empty string in VwV language, which consists only of lowercase Latin letters 'v' and 'w'. The length of the string does not exceed 100.

Output

For each testcase print a single integer: the minimum number of letters Polycarp should underline so that there is no ambiguity in his notes.

Example

Input


5
vv
v
w
vwv
vwvvwv


Output


1
0
1
1
3

Note

In the first testcase it's enough to underline any of the two letters 'v'.

In the second testcase the letter 'v' is not ambiguous by itself already, so you don't have to underline anything.

In the third testcase you have to underline 'w', so that you don't mix it up with two letters 'v'.

In the fourth testcase you can underline 'w' to avoid all the ambiguity.

In the fifth testcase you can underline both letters 'w' and any of the two letters 'v' between them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given an array $a_1, \ldots, a_n$ of $n$ non-negative integers.

Let's call it sharpened if and only if there exists an integer $1 \le k \le n$ such that $a_1 < a_2 < \ldots < a_k$ and $a_k > a_{k+1} > \ldots > a_n$. In particular, any strictly increasing or strictly decreasing array is sharpened. For example:  The arrays $[4]$, $[0, 1]$, $[12, 10, 8]$ and $[3, 11, 15, 9, 7, 4]$ are sharpened;  The arrays $[2, 8, 2, 8, 6, 5]$, $[0, 1, 1, 0]$ and $[2, 5, 6, 9, 8, 8]$ are not sharpened. 

You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any $i$ ($1 \le i \le n$) such that $a_i>0$ and assign $a_i := a_i - 1$.

Tell if it's possible to make the given array sharpened using some number (possibly zero) of these operations.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 15\ 000$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line of each test case contains a sequence of $n$ non-negative integers $a_1, \ldots, a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case, output a single line containing "Yes" (without quotes) if it's possible to make the given array sharpened using the described operations, or "No" (without quotes) otherwise.


-----Example-----
Input
10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1

Output
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No



-----Note-----

In the first and the second test case of the first test, the given array is already sharpened.

In the third test case of the first test, we can transform the array into $[3, 11, 15, 9, 7, 4]$ (decrease the first element $97$ times and decrease the last element $4$ times). It is sharpened because $3 < 11 < 15$ and $15 > 9 > 7 > 4$.

In the fourth test case of the first test, it's impossible to make the given array sharpened.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a rooted binary tree with $n$ vertices containing numbers. Each vertex of the tree either has two sons (left son and right son), or no sons. We will call such a tree heap, if and only if for all vertices (except the root), the number assigned the vertex is smaller or equal to the parent's number.

Consider a heap and the following function:

dfs(vertex){
    print number in the vertex
    if (vertex is not a leaf) {
        dfs(left son of the vertex)
        dfs(right son of the vertex)
    }
}

You are given a sequence $a[1..n]$ of $n$ numbers. Your task is to calculate how many heaps will produce this sequence after calling dfs(root). It is guaranteed that the sequence is generated by generate() function listed in the input format section below. Since the number of heaps can be very large, output its value modulo $10000007\ (10^9+7)$.

Constraints

$1\leq n<2\times10^5$ 

$1\leq a_i\leq n$

Input Format

The first line contains a single odd integer $n$. The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ $\textbf{—}$ the result of dfs(root) call.

The sequence is generated by this algorithm:

int n, k, ptr
array of integers a[1 .. n]

generate(){
    read odd n
    create array val[1 .. n]
    for each i from 1 to n
        val[i] = random(1, n) //random(l, r) returns uniform integer from [l, r]
    ptr = 1
    sort array val by non-increasing
    gen_heap(val)
}

gen_heap(array values){
    k = size of values
    a[ptr] = values[1]
    ptr = ptr + 1
    if(k == 1)
        return
    create two empty arrays left, right
    for each i from 2 to k - 1
        if(random(1, 2) == 1){
            add values[i] to the end of left
        }else{
            add values[i] to the end of right
        }
    if(left has even size)
        add values[k] to the end of left
    else
        add values[k] to the end of right
    gen_heap(left);
    gen_heap(right);
}

Output Format

Output the number of heaps that will produce the given sequence modulo $10000007\ (10^9+7)$.

Sample Input
5
2 1 1 1 1

Sample Output

2

Explanation

There are two different heaps:

    2               2
   / \             / \
  1   1           1   1
     / \         / \
    1   1       1   1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n students in Polycarp's class (including himself). A few days ago all students wrote an essay "My best friend". Each student's essay was dedicated to one of the students of class, to his/her best friend. Note that student b's best friend is not necessarily student a, if a's best friend is b.

And now the teacher leads the whole class to the museum of the history of sports programming. Exciting stories of legendary heroes await the students: tourist, Petr, tomek, SnapDragon — that's who they will hear about!

The teacher decided to divide students into pairs so that each pair consisted of a student and his best friend. She may not be able to split all the students into pairs, it's not a problem — she wants to pick out the maximum number of such pairs. If there is more than one variant of doing so, she wants to pick out the pairs so that there were as much boy-girl pairs as possible. Of course, each student must not be included in more than one pair.

Input

The first line contains an integer n (2 ≤ n ≤ 105), n is the number of students per class. Next, n lines contain information about the students, one per line. Each line contains two integers fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2), where fi is the number of i-th student's best friend and si denotes the i-th pupil's sex (si = 1 for a boy and si = 2 for a girl).

Output

Print on the first line two numbers t, e, where t is the maximum number of formed pairs, and e is the maximum number of boy-girl type pairs among them. Then print t lines, each line must contain a pair ai, bi (1 ≤ ai, bi ≤ n), they are numbers of pupils in the i-th pair. Print the pairs in any order. Print the numbers in pairs in any order. If there are several solutions, output any of them.

Examples

Input

5
5 2
3 2
5 1
2 1
4 2


Output

2 2
5 3
4 2


Input

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


Output

3 1
4 2
5 1
3 6


Input

8
2 2
3 2
5 1
3 1
6 1
5 1
8 2
7 1


Output

4 1
5 6
3 4
2 1
7 8

Note

The picture corresponds to the first sample. On the picture rhomb stand for boys, squares stand for girls, arrows lead from a pupil to his/her best friend. Bold non-dashed arrows stand for pairs in the answer. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Natural numbers from 1 to N have been placed in an increasing order over some helix ( a circular structure ). When the helix starts rotating, it is easy to find out 

The position of a given number
The number located at a given position. 

The helix has numbers arranged in the following fashion:  

[1, 2, 3, ..., N]

Due to some malfunction, the helix has started rotating in a weird manner. Right now, every possible contiguous interval can be rotated, and hence, locating a particular number or identifying the number at a given position is almost impossible. For example, if at some particular instant, the integer list is like this:

[1, 2, 3, 4, 5, ..., N]

rotating the interval [5...N] will leave the list like this:

[1, 2, 3, 4, N, N - 1, N - 2, ..., 5]

We need a software to handle this. Can you help us?

Input Format 

The first line of the input consists of two space separated integers, N, Q. N signifies that initially our list contains numbers from 1 to N, placed in an increasing order. Q lines follow and contain input in one of the following formats:  

1 A B

indicating that the helix rotated circularly in the interval [A..B] ( both inclusive);

2 A

indicating that we are interested in knowing the current position of the number A  

3 A

indicating that we are interested in knowing the number at position A.  

Output Format 

For each line in the input of the form 2 A  

output a line saying 

element A is at position x

where A is the number we are interested in and x is its current position.

For each line of the form 3 A

output a line saying 

element at position A is x

where A is the position we are interested in and x is the integer located at this position. 

Constraints  

1 ≤ N, Q ≤ $10^{5}$ 

positions are 1-indexed.   

Sample Input

5 10
1 1 3
2 3
3 3
1 3 5
1 2 4
3 1
3 5
2 4
1 5 5
2 2

Sample Output

element 3 is at position 1
element at position 3 is 1
element at position 1 is 3
element at position 5 is 1
element 4 is at position 2
element 2 is at position 4

Explanation

Initially elements are placed like this:

[1, 2, 3, 4, 5]

after the first rotation, they are placed like this:

[3, 2, 1, 4, 5]

and that's how we get the first 2 results (first 2 lines in the output). After second rotation, they are placed like this:

[3, 2, 5, 4, 1]

and third one does this:

[3, 4, 5, 2, 1]

In the last rotation (1 5 5), it's easy to see that output matches the initial positions of the elements. Last rotation doesn't change the positions of the elements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’ve just come out of a theatre after watching X-Men, and you’re thinking of mutation. You cannot just move on. You’re stuck on mutation, and its issues. But unlike mutants in the movie, you’re just another Mathematician, with the four basic powers:  
Addition
Subtraction
Division
Multiplication

And with every power there’s associated a number. And you are allowed to use only the number associated with a power, when using that power. After deciding all those rules, and powers, you feel better about yourself and decide to take on the task of converting one number to another, using your powers. But, here’s the tricky part -   

NOTE:
All calculations done using your powers should be done in a way so that they never exceed 1000000 and should  never go below 2 as well.

You’ve to output the minimum number of  minimum number of   steps to reach from a to b using powers.  

input:
First line of input contains T, number of test cases . Each test case contains two lines , first line contains two integers a and b, second line contains four integer that Mul, Div, Add and Sub numbers associated with power of Multiplication, Division, Addition and Subtraction.  

Output:
For each test case print the minimum number of   steps to reach from a to b using powers, if not possible print -1 .  

Constraints:
1 ≤ T ≤ 100
1 ≤ a ≤ b ≤ 10000
1 ≤ Mul ≤ Div ≤ 1000  
0 ≤ Add ≤ Sub ≤ 1000  

SAMPLE INPUT
3
2 4
2 1 1 1
2 4
1 2 3 4
2 5
1 2 3 4

SAMPLE OUTPUT
1
3
1

Explanation

Test Case#1:
Source= 2 and Destination=4
Value of Mul=2, Div=1, Add=1 and Sub=1
You can go from source to destination with one step that is 2*2=4.   

Test Case#2:
Source=2 and Destination =4 
Value of Mul=1, Div=2, Add=3 and Sub=4
Then the possible path will be:
Step1:  2+3 = 5
Step2:  5+3 = 8
Step3:  8/2= 4

Note: You can't use Div operation is first step because *All calculations done using your powers should be done in a way so that they never exceed 1000000 and should never go below 2 as well.
*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Did you know that the people of America eat around 100 acres of pizza per day ? Having read this fact on internet, two chefs from the Elephant city, Arjuna and Bhima are set to make pizza popular in India. They organized a social awareness camp, where N people ( other than these two ) sit around a large pizza. To make it more interesting, they make some pairs among these N people and the two persons in a pair, feed each other.

Each person should be a part of at most one pair and most importantly, to make feeding easy, any two pairs should not cross each other ( see figure for more clarity ). Arjuna and Bhima decided to play a game on making the pairs. In his turn, a player makes a pair ( selects two persons, as long as its valid ) and this pair start feeding each other. Arjuna and Bhima take turns alternately, by making a pair in each turn, and they  play optimally ( see Notes for more clarity ). The one who can not make a pair in his turn, loses. Given N, find who wins the game, if Arjuna starts first. 

-----Notes-----
- 'Optimally' means, if there is a possible move a person can take in his turn that can make him win finally, he will always take that. You can assume both are very intelligent. 

-----Input-----
First line contains an integer T ( number of test cases, around 1000 ). Each of the next T lines contains an integer N ( 2 <= N <= 10000 )

-----Output-----
For each test case, output the name of the winner ( either "Arjuna" or "Bhima" ( without quotes ) ) in a new line.

-----Example-----
Input:
4
2
4
5
6

Output:
Arjuna
Arjuna
Bhima
Arjuna

Explanation:

Let the people around the table are numbered 1, 2, ... , N in clock-wise order as shown in the image 

Case 1 : N = 2. Only two persons and Arjuna makes the only possible pair (1,2)

Case 2 : N = 4. Arjuna can make the pair (1,3). Bhima can not make any more pairs ( without crossing the pair (1,3) )

Case 3 : N = 5. No matter which pair Arjuna makes first, Bhima can always make one more pair, and Arjuna can not make any further

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
David is writing an article for the Bulletin of the Association of Proof Completions. In his article, he proves several theorems. For every theorem, David came up with a proof. Since David is a very eager student, he even came up with multiple proofs for some of the theorems. As usual, a proof for a theorem may depend on a number of other theorems.

The article has to be as short as possible to publish it, and David only really cares about the main theorem, Theorem $0$. In order to achieve this, he has estimated the number of words he will need for every proof. Can you help David find the shortest possible length of his article?

-----Input-----
 - A single line containing $1\leq n\leq 20$, the number of theorems.
 - For each theorem:
 - A single line containing $1\leq p_ i\leq 10$, the number of proofs for the $i$th theorem.
 - $p_ i$ lines, each of the form $l$, $k$, $d_0,\dots ,d_{k-1}$, where $0\leq l\leq 10^6$ is the length of the proof, $0\leq k\leq n-1$ is the number of theorems the proof depends on, and the $0\leq d_ i\leq n-1$ are the numbers of the theorems the proof depends on.

-----Output-----
Print one line with a single integer, the shortest possible length of David’s article.

-----Examples-----
Sample Input:
2
2
10 0
3 1 1
1
4 1 0
Sample Output:
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently your town has been infested by swindlers who convince unknowing tourists to play a simple dice game with them for money. The game works as follows: given is an $n$-sided die, whose sides have $1, 2, \ldots , n$ pips, and a positive integer $k$. You then roll the die, and then have to make a choice. Option $1$ is to stop rolling. Option $2$ is to reroll the die, with the limitation that the die can only be rolled $k$ times in total. Your score is the number of pips showing on your final roll.

Obviously the swindlers are better at this game than the tourists are. You, proud supporter of the Battle Against Probabilistic Catastrophes, decide to fight this problem not by banning the swindlers but by arming the tourists with information.

You create pamphlets on which tourists can find the maximum expected score for many values of $n$ and $k$. You are sure that the swindlers will soon stop their swindling if the tourists are better prepared than they are!

The layout of the flyers is done, and you have distribution channels set up. All that is left to do is to calculate the numbers to put on the pamphlet.

Given the number of sides of the die and the number of times you are allowed to roll, calculate the expected (that is, average) score when the game is played optimally.

-----Input-----
 - A single line with two integers $1\leq n\leq 100$, the number of sides of the die, and $1\leq k\leq 100$, the number of times the die may be rolled.

-----Output-----
Output the expected score when playing optimally. Your answer should have an absolute or relative error of at most $10^{-7}$.

-----Examples-----
Sample Input 1:
1 1
Sample Output 1:
1

Sample Input 2:
2 3
Sample Output 2:
1.875

Sample Input 3:
6 2
Sample Output 3:
4.25

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are n different books, numbered 1 through n.

We will look at the library's operation during n consecutive days. Heidi knows in advance that on the i-th day (1 ≤ i ≤ n) precisely one person will come to the library, request to borrow the book a_{i}, read it in a few hours, and return the book later on the same day.

Heidi desperately wants to please all her guests, so she will make sure to always have the book a_{i} available in the library on the i-th day. During the night before the i-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.

There is a problem, though. The capacity of the library is k – this means that at any time, there can be at most k books at the library. If buying a new book would cause Heidi to have more than k books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.

You are given k and the sequence of requests for books a_1, a_2, ..., a_{n}. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?


-----Input-----

The first line of input will contain two integers n and k (1 ≤ n, k ≤ 80). The second line will contain n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) – the sequence of book requests.


-----Output-----

On a single line print the minimum cost of buying books at the store so as to satisfy all requests.


-----Examples-----
Input
4 80
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3



-----Note-----

In the first test case, Heidi is able to keep all books forever. Therefore, she only needs to buy the book 1 before the first day and the book 2 before the second day.

In the second test case, she can only keep one book at a time. Therefore she will need to buy new books on the first, second and fourth day.

In the third test case, before buying book 3 on the third day, she must decide which of the books 1 and 2 she should get rid of. Of course, she should keep the book 1, which will be requested on the fourth day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vasya's Calendar

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya lives in a strange world. The year has *n* months and the *i*-th month has *a**i* days. Vasya got a New Year present — the clock that shows not only the time, but also the date.

The clock's face can display any number from 1 to *d*. It is guaranteed that *a**i*<=≤<=*d* for all *i* from 1 to *n*. The clock does not keep information about the current month, so when a new day comes, it simply increases the current day number by one. The clock cannot display number *d*<=+<=1, so after day number *d* it shows day 1 (the current day counter resets). The mechanism of the clock allows you to increase the day number by one manually. When you execute this operation, day *d* is also followed by day 1.

Vasya begins each day checking the day number on the clock. If the day number on the clock does not match the actual day number in the current month, then Vasya manually increases it by one. Vasya is persistent and repeats this operation until the day number on the clock matches the actual number of the current day in the current month.

A year passed and Vasya wonders how many times he manually increased the day number by one, from the first day of the first month to the last day of the *n*-th month inclusive, considering that on the first day of the first month the clock display showed day 1.

Input Specification:
The first line contains the single number *d* — the maximum number of the day that Vasya's clock can show (1<=≤<=*d*<=≤<=106).

The second line contains a single integer *n* — the number of months in the year (1<=≤<=*n*<=≤<=2000).

The third line contains *n* space-separated integers: *a**i* (1<=≤<=*a**i*<=≤<=*d*) — the number of days in each month in the order in which they follow, starting from the first one.

Output Specification:
Print a single number — the number of times Vasya manually increased the day number by one throughout the last year.

Demo Input:
['4\n2\n2 2\n', '5\n3\n3 4 3\n', '31\n12\n31 28 31 30 31 30 31 31 30 31 30 31\n']

Demo Output:
['2\n', '3\n', '7\n']

Note:
In the first sample the situation is like this: 
 -  Day 1. Month 1. The clock shows 1. Vasya changes nothing. -  Day 2. Month 1. The clock shows 2. Vasya changes nothing. -  Day 1. Month 2. The clock shows 3. Vasya manually increases the day number by 1. After that the clock shows 4. Vasya increases the day number by 1 manually. After that the clock shows 1. -  Day 2. Month 2. The clock shows 2. Vasya changes nothing.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.