vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
After his wife's tragic death, Eurydice, Orpheus descended to the realm of death to see her. Reaching its gates was uneasy, but passing through them proved to be even more challenging. Mostly because of Cerberus, the three-headed hound of Hades. 

Orpheus, a famous poet, and musician plans to calm Cerberus with his poetry and safely walk past him. He created a very peculiar poem for Cerberus. It consists only of lowercase English letters. 

We call a poem's substring a palindrome if and only if it reads the same backwards and forwards. A string a is a substring of a string b if a can be obtained from b by deleting several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

Unfortunately, Cerberus dislikes palindromes of length greater than 1. For example in the poem abaa the hound of Hades wouldn't like substrings aba and aa.

Orpheus can only calm Cerberus if the hound likes his poetry. That's why he wants to change his poem so that it does not contain any palindrome substrings of length greater than 1.

Orpheus can modify the poem by replacing a letter at any position with any lowercase English letter. He can use this operation arbitrarily many times (possibly zero). Since there can be many palindromes in his poem, he may have to make some corrections. But how many, exactly? Given the poem, determine the minimal number of letters that have to be changed so that the poem does not contain any palindromes of length greater than 1.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 10^5) denoting the number of test cases, then t test cases follow.

The first and only line of each test case contains a non-empty string of lowercase English letters, Orpheus' poem.

The sum of the length of Orpheus' poems in all test cases will not exceed 10^5.

Output

You should output t lines, i-th line should contain a single integer, answer to the i-th test case.

Example

Input


7
babba
abaac
codeforces
zeroorez
abcdcba
bbbbbbb
a


Output


1
1
0
1
1
4
0

Note

In the first test case, we can replace the third character with c and obtain a palindrome-less poem bacba.

In the second test case, we can replace the third character with d and obtain a palindrome-less poem abdac.

In the third test case, the initial poem already doesn't contain any palindromes, so Orpheus doesn't need to change anything there.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Max wants to buy a new skateboard. He has calculated the amount of money that is needed to buy a new skateboard. He left a calculator on the floor and went to ask some money from his parents. Meanwhile his little brother Yusuf came and started to press the keys randomly. Unfortunately Max has forgotten the number which he had calculated. The only thing he knows is that the number is divisible by 4.

You are given a string s consisting of digits (the number on the display of the calculator after Yusuf randomly pressed the keys). Your task is to find the number of substrings which are divisible by 4. A substring can start with a zero.

A substring of a string is a nonempty sequence of consecutive characters.

For example if string s is 124 then we have four substrings that are divisible by 4: 12, 4, 24 and 124. For the string 04 the answer is three: 0, 4, 04.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The only line contains string s (1 ≤ |s| ≤ 3·105). The string s contains only digits from 0 to 9.

Output

Print integer a — the number of substrings of the string s that are divisible by 4.

Note that the answer can be huge, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Examples

Input

124


Output

4


Input

04


Output

3


Input

5810438174


Output

9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Dishonest Sellers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Igor found out discounts in a shop and decided to buy *n* items. Discounts at the store will last for a week and Igor knows about each item that its price now is *a**i*, and after a week of discounts its price will be *b**i*.

Not all of sellers are honest, so now some products could be more expensive than after a week of discounts.

Igor decided that buy at least *k* of items now, but wait with the rest of the week in order to save money as much as possible. Your task is to determine the minimum money that Igor can spend to buy all *n* items.

Input Specification:
In the first line there are two positive integer numbers *n* and *k* (1<=≤<=*n*<=≤<=2·105, 0<=≤<=*k*<=≤<=*n*) — total number of items to buy and minimal number of items Igor wants to by right now.

The second line contains sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=104) — prices of items during discounts (i.e. right now).

The third line contains sequence of integers *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=104) — prices of items after discounts (i.e. after a week).

Output Specification:
Print the minimal amount of money Igor will spend to buy all *n* items. Remember, he should buy at least *k* items right now.

Demo Input:
['3 1\n5 4 6\n3 1 5\n', '5 3\n3 4 7 10 3\n4 5 5 12 5\n']

Demo Output:
['10\n', '25\n']

Note:
In the first example Igor should buy item 3 paying 6. But items 1 and 2 he should buy after a week. He will pay 3 and 1 for them. So in total he will pay 6 + 3 + 1 = 10.

In the second example Igor should buy right now items 1, 2, 4 and 5, paying for them 3, 4, 10 and 3, respectively. Item 3 he should buy after a week of discounts, he will pay 5 for it. In total he will spend 3 + 4 + 10 + 3 + 5 = 25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rishi likes to play with strings.Strings have been his passion since his childhood.One day in college,Rishi came to know about the contest - International Strings Olympiad.Since then he has been determined to work on his passion and win the Olympiad.
Today Rishi has got stuck in an interesting problem.Help him solve that.

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of operations required to convert ‘str1′ into ‘str2′.

The operations can be any of the following types:

->Insert

->Remove

->Replace

All of the above operations are of equal cost.

Input

The first line contains string str1 (length of str1 is ≤140)

The second line contains string str2 (length of str2 is ≤140)

Output

Print minimum number of operations required to convert ‘str1′ into ‘str2′. 

SAMPLE INPUT
rish
rishi

SAMPLE OUTPUT
1

Explanation

We can convert rish into rishi by inserting a 'i'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Greg got a grid with n rows and m columns. Rows are indexed from 1 to n and columns are indexed from 1 to m. The cell $ ( i , j )$ is the cell of intersection of row i and column j. Each cell has a number written on it. The number written on cell  $( i , j )$  is equal to  $(i+j)$.  
Now, Greg wants to select some cells from the grid, such that for every pair of  selected cells ,the numbers on the cells are co-prime.  Determine the maximum number of cells that Greg can select.

------ Input  ------ 

Single line containing  integers n and m denoting number of rows and number of columns respectively.

------ Output ------ 

Single line containing the answer.

------ Constraints ------ 

$$1 ≤ n,m ≤ 10^{6}$$

----- Sample Input 1 ------ 
3 4

----- Sample Output 1 ------ 
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, [1], [4, 3, 5, 1, 2], [3, 2, 1] — are permutations, and [1, 1], [4, 3, 1], [2, 3, 4] — no.

Permutation a is lexicographically smaller than permutation b (they have the same length n), if in the first index i in which they differ, a[i] < b[i]. For example, the permutation [1, 3, 2, 4] is lexicographically smaller than the permutation [1, 3, 4, 2], because the first two elements are equal, and the third element in the first permutation is smaller than in the second.

The next permutation for a permutation a of length n — is the lexicographically smallest permutation b of length n that lexicographically larger than a. For example: 

  * for permutation [2, 1, 4, 3] the next permutation is [2, 3, 1, 4]; 
  * for permutation [1, 2, 3] the next permutation is [1, 3, 2]; 
  * for permutation [2, 1] next permutation does not exist. 



You are given the number n — the length of the initial permutation. The initial permutation has the form a = [1, 2, …, n]. In other words, a[i] = i (1 ≤ i ≤ n).

You need to process q queries of two types: 

  * 1 l r: query for the sum of all elements on the segment [l, r]. More formally, you need to find a[l] + a[l + 1] + … + a[r]. 
  * 2 x: x times replace the current permutation with the next permutation. For example, if x=2 and the current permutation has the form [1, 3, 4, 2], then we should perform such a chain of replacements [1, 3, 4, 2] → [1, 4, 2, 3] → [1, 4, 3, 2]. 



For each query of the 1-st type output the required sum.

Input

The first line contains two integers n (2 ≤ n ≤ 2 ⋅ 10^5) and q (1 ≤ q ≤ 2 ⋅ 10^5), where n — the length of the initial permutation, and q — the number of queries.

The next q lines contain a single query of the 1-st or 2-nd type. The 1-st type query consists of three integers 1, l and r (1 ≤ l ≤ r ≤ n), the 2-nd type query consists of two integers 2 and x (1 ≤ x ≤ 10^5).

It is guaranteed that all requests of the 2-nd type are possible to process.

Output

For each query of the 1-st type, output on a separate line one integer — the required sum.

Example

Input


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


Output


9
4
6

Note

Initially, the permutation has the form [1, 2, 3, 4]. Queries processing is as follows: 

  1. 2 + 3 + 4 = 9; 
  2. [1, 2, 3, 4] → [1, 2, 4, 3] → [1, 3, 2, 4] → [1, 3, 4, 2]; 
  3. 1 + 3 = 4; 
  4. 4 + 2 = 6 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair $(a, b) \in \rho$, in this case we use a notation $a \stackrel{\rho}{\sim} b$.

Binary relation is equivalence relation, if: It is reflexive (for any a it is true that $a \stackrel{\rho}{\sim} a$); It is symmetric (for any a, b it is true that if $a \stackrel{\rho}{\sim} b$, then $b \stackrel{\rho}{\sim} a$); It is transitive (if $a \stackrel{\rho}{\sim} b$ and $b \stackrel{\rho}{\sim} c$, than $a \stackrel{\rho}{\sim} c$).

Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his "proof":

Take any two elements, a and b. If $a \stackrel{\rho}{\sim} b$, then $b \stackrel{\rho}{\sim} a$ (according to property (2)), which means $a \stackrel{\rho}{\sim} a$ (according to property (3)).

It's very simple, isn't it? However, you noticed that Johnny's "proof" is wrong, and decided to show him a lot of examples that prove him wrong.

Here's your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).

Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 10^9 + 7.


-----Input-----

A single line contains a single integer n (1 ≤ n ≤ 4000).


-----Output-----

In a single line print the answer to the problem modulo 10^9 + 7.


-----Examples-----
Input
1

Output
1

Input
2

Output
3

Input
3

Output
10



-----Note-----

If n = 1 there is only one such relation — an empty one, i.e. $\rho = \varnothing$. In other words, for a single element x of set A the following is hold: [Image].

If n = 2 there are three such relations. Let's assume that set A consists of two elements, x and y. Then the valid relations are $\rho = \varnothing$, ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A *Vampire number* is a positive integer `z` with a factorization `x * y = z` such that

- `x` and `y` have the same number of digits and
- the multiset of digits of `z` is equal to the multiset of digits of `x` and `y`.
- Additionally, to avoid trivialities, `x` and `y` may not both end with `0`.

In this case, `x` and `y` are called *fangs* of `z`. (The fangs of a Vampire number may not be unique, but this shouldn't bother us.) The first three Vampire numbers are

```
1260 = 21*60
1395 = 15*93
1435 = 35*41
```

Write an algorithm that on input `k` returns the `k`th Vampire number. To avoid time-outs, the Python version will test with `1 <= k <= 155`.

PS: In the OEIS, the Vampire numbers are sequence [A014575](https://oeis.org/A014575).

PPS: So called *Pseudo-Vampire Numbers* are treated in [this kata](http://www.codewars.com/kata/vampire-numbers-1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Voting for Photos

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After celebrating the midcourse the students of one of the faculties of the Berland State University decided to conduct a vote for the best photo. They published the photos in the social network and agreed on the rules to choose a winner: the photo which gets most likes wins. If multiple photoes get most likes, the winner is the photo that gets this number first.

Help guys determine the winner photo by the records of likes.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the total likes to the published photoes. 

The second line contains *n* positive integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1<=000<=000), where *a**i* is the identifier of the photo which got the *i*-th like.

Output Specification:
Print the identifier of the photo which won the elections.

Demo Input:
['5\n1 3 2 2 1\n', '9\n100 200 300 200 100 300 300 100 200\n']

Demo Output:
['2\n', '300\n']

Note:
In the first test sample the photo with id 1 got two likes (first and fifth), photo with id 2 got two likes (third and fourth), and photo with id 3 got one like (second). 

Thus, the winner is the photo with identifier 2, as it got:
 -  more likes than the photo with id 3; -  as many likes as the photo with id 1, but the photo with the identifier 2 got its second like earlier.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Susan is making high-speed videos of falling coffee mugs. When analyzing the videos she wants to know how big the mugs are, but unfortunately they all got destroyed during filming. Susan knows some physics though, so she has figured out how far they moved between different video frames. The camera was filming at a speed of $70$ frames per second, which means that at frame $n$, counted from when the mug was released, the number of millimeters it has moved is $d=n^2$. The counting of the frames starts at $0$.

Susan thinks a certain mug is $D$ millimeters high, but to verify this she needs to find two frames between which the mug has moved exactly this distance. Can you help her do this?

-----Input-----
The input file contains the single positive integer $D\leq 200000$, the distance to be measured.

-----Output-----
Output two non-negative integers $n_1$ and $n_2$, the numbers of the frames that Susan should compare. They should fulfill $n_2^2-n_1^2=D$. If no two such integers exist, instead output “impossible”.

-----Examples-----
Sample Input:
88
Sample Output:
9 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recall that a permutation of length $n$ is an array where each element from $1$ to $n$ occurs exactly once.

For a fixed positive integer $d$, let's define the cost of the permutation $p$ of length $n$ as the number of indices $i$ $(1 \le i < n)$ such that $p_i \cdot d = p_{i + 1}$.

For example, if $d = 3$ and $p = [5, 2, 6, 7, 1, 3, 4]$, then the cost of such a permutation is $2$, because $p_2 \cdot 3 = p_3$ and $p_5 \cdot 3 = p_6$.

Your task is the following one: for a given value $n$, find the permutation of length $n$ and the value $d$ with maximum possible cost (over all ways to choose the permutation and $d$). If there are multiple answers, then print any of them.


-----Input-----

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

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

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the value $d$ in the first line, and $n$ integers in the second line — the permutation itself. If there are multiple answers, then print any of them.


-----Examples-----

Input
2
2
3
Output
2
1 2
3
2 1 3


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is participating in a programming contest called AXC002, and he has just submitted his code to Problem A.
The problem has N test cases.
For each test case i (1\leq i \leq N), you are given a string S_i representing the verdict for that test case. Find the numbers of test cases for which the verdict is AC, WA, TLE, and RE, respectively.
See the Output section for the output format.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - S_i is AC, WA, TLE, or RE.

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
\vdots
S_N

-----Output-----
Let C_0, C_1, C_2, and C_3 be the numbers of test cases for which the verdict is AC, WA, TLE, and RE, respectively. Print the following:
AC x C_0
WA x C_1
TLE x C_2
RE x C_3

-----Sample Input-----
6
AC
TLE
AC
AC
WA
TLE

-----Sample Output-----
AC x 3
WA x 1
TLE x 2
RE x 0

We have 3, 1, 2, and 0 test case(s) for which the verdict is AC, WA, TLE, and RE, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of `n` segments on the axis `Ox`, each segment has integer endpoints between `0` and `m` inclusive.
 Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers li and ri — coordinates of the left and of the right endpoints.

 Consider all integer points between `0` and `m` inclusive. Your task is to print all such points that don't belong to any segment. The point x belongs to the segment `[l;r]` if and only if `l ≤ x ≤ r`.

**Input:**
 `m` — the upper bound for coordinates;
 array of coordinates li and ri `0 ≤ li ≤ ri ≤ m` — the endpoints of the `i`-th segment. Segments may intersect, overlap or even coincide with each other.

**Output:**
 All points from `0` to `m` that don't belong to any segment.

**Examples:**
```python
segments(5, [(2,2),(1,2),(5,5)]) => [0,3,4]
segments(7, [(0,7)]) => []
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Salazar Slytherin's Locket

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher. 

Harry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers *l* and *r* (both inclusive). 

Harry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base *b*, all the digits from 0 to *b*<=-<=1 appear even number of times in its representation without any leading zeros.

You have to answer *q* queries to unlock the office. Each query has three integers *b**i*, *l**i* and *r**i*, the base and the range for which you have to find the count of magic numbers.

Input Specification:
First line of input contains *q* (1<=≤<=*q*<=≤<=105) — number of queries.

Each of the next *q* lines contain three space separated integers *b**i*, *l**i*, *r**i* (2<=≤<=*b**i*<=≤<=10, 1<=≤<=*l**i*<=≤<=*r**i*<=≤<=1018).

Output Specification:
You have to output *q* lines, each containing a single integer, the answer to the corresponding query.

Demo Input:
['2\n2 4 9\n3 1 10\n', '2\n2 1 100\n5 1 100\n']

Demo Output:
['1\n2\n', '21\n4\n']

Note:
In sample test case 1, for first query, when we convert numbers 4 to 9 into base 2, we get: 
 -  4 = 100<sub class="lower-index">2</sub>, -  5 = 101<sub class="lower-index">2</sub>, -  6 = 110<sub class="lower-index">2</sub>, -  7 = 111<sub class="lower-index">2</sub>, -  8 = 1000<sub class="lower-index">2</sub>, -  9 = 1001<sub class="lower-index">2</sub>. 
Out of these, only base 2 representation of 9 has even number of 1 and 0. Thus, the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given two numbers `m,n`. The numbers could span from `0` to `10000`. We can get their product by using binary reduction as show in the table below.
Example (to understand the table please read the description below it) 





real value of m(r)
m
n
(r*n)


0
100
15
0


0
50
30
0


1
25
60
60


0
12
120
0


0
6
240
0


1
3
480
480


1
1
960
960



Above, we are given two numbers `100` and `15`. we keep reducing the bigger number by dividing it by `2` and hold the integer part of the division till it is no more divisible by `2`. Then we assign the real values to these reduced parts of `m`. Any reduced number `[1,m]` has real value of `0` if it is even, and it will have real value of `1` if it is odd. On the other hand the smaller number in this case `n` keeps on doubling itself the same amount of times `m` reduces itself. The idea of this method is to change multiplication of two big number to a sequence of multiplication by `0` or `1` and perform addition to get the final product. You can see that from the last column `(r*n)` above. 
if we sum the last column we get `0+60+0+0+480+960=1500=100*15`
Now your task for this kata will be to get those non-zero number in the last column in an array and return it sorted in descending order.so for the above example the return will be `[960,480,60]`.

_Beware: _`m,n`_ are not necessarily ordered._

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