vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Today is Wednesday, the third day of the week. What's more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn't sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.


-----Input-----

The only line of the input is in one of the following two formats:   "x of week" where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.  "x of month" where x (1 ≤ x ≤ 31) denotes the day of the month. 


-----Output-----

Print one integer — the number of candies Limak will save in the year 2016.


-----Examples-----
Input
4 of week

Output
52

Input
30 of month

Output
11



-----Note-----

Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole *n* ordered piles of worms such that *i*-th pile contains *a**i* worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to *a*1, worms in second pile are labeled with numbers *a*1<=+<=1 to *a*1<=+<=*a*2 and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105), the number of piles.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=103, *a*1<=+<=*a*2<=+<=...<=+<=*a**n*<=≤<=106), where *a**i* is the number of worms in the *i*-th pile.

The third line contains single integer *m* (1<=≤<=*m*<=≤<=105), the number of juicy worms said by Marmot.

The fourth line contains *m* integers *q*1,<=*q*2,<=...,<=*q**m* (1<=≤<=*q**i*<=≤<=*a*1<=+<=*a*2<=+<=...<=+<=*a**n*), the labels of the juicy worms.

Output Specification:
Print *m* lines to the standard output. The *i*-th line should contain an integer, representing the number of the pile where the worm labeled with the number *q**i* is.

Demo Input:
['5\n2 7 3 4 9\n3\n1 25 11\n']

Demo Output:
['1\n5\n3\n']

Note:
For the sample input:
 -  The worms with labels from [1, 2] are in the first pile. -  The worms with labels from [3, 9] are in the second pile. -  The worms with labels from [10, 12] are in the third pile. -  The worms with labels from [13, 16] are in the fourth pile. -  The worms with labels from [17, 25] are in the fifth pile.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.




Example 2:

Input: S = "2-5g-3-J", K = 2

Output: "2-5G-3J"

Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.



Note:

The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has just found a recipe book, where every dish consists of exactly four ingredients.
He is going to choose some two dishes and prepare them for dinner.
Of course, he likes diversity and wants to know whether the two dishes are similar.
Two dishes are called similar if at least half of their ingredients are the same.
In other words, at least two of four ingredients of the first dish should also be present in the second dish.
The order of ingredients doesn't matter.
Your task is to examine T pairs of dishes.
For each pair, check if the two dishes are similar and print "similar" or "dissimilar" accordingly.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains four distinct strings, denoting ingredients needed for the first dish.
Each ingredient is represented by a string of length between 2 and 10 inclusive, consisting of lowercase English letters.

The second line of each test case describes the second dish in the same format.

-----Output-----
For each test case, output a single line containing the answer — "similar" if at least half of the ingredients are same, and "dissimilar" otherwise (without the quotes).

-----Constraints-----
- 1 ≤ T ≤ 200
- The length of each string will be between 2 and 10 inclusive.

-----Example-----
Input:
5
eggs sugar flour salt
sugar eggs milk flour
aa ab ac ad
ac ad ae af
cookies sugar grass lemon
lemon meat chili wood
one two three four
one two three four
gibberish jibberish lalalalala popopopopo
jibberisz gibberisz popopopopu lalalalalu

Output:
similar
similar
dissimilar
similar
dissimilar

-----Explanation-----
Test case 1. The first dish consists of ingredients: eggs, sugar, flour, salt, while the second dish consists of: sugar, eggs, milk, flour. Three of four ingredients are present in both dishes (eggs, sugar, flour) so the two dishes are similar.
Test case 2. This example shows that strings in the input don't necessarily represent real food.
The answer is again "similar", because two ingredients are present in both dishes ("ac" and "ad").
Test case 3. The only common ingredient is lemon, so the answer is "dissimilar".
Remember that at least two ingredients should be present in both dishes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon likes strings. Today he created a game about strings:

String s_1, s_2, …, s_n is beautiful if and only if for each 1 ≤ i < n, s_i ≠ s_{i+1}.

Initially, Dreamoon has a string a. In each step Dreamoon can choose a beautiful substring of a and remove it. Then he should concatenate the remaining characters (in the same order).

Dreamoon wants to use the smallest number of steps to make a empty. Please help Dreamoon, and print any sequence of the smallest number of steps to make a empty.

Input

The first line contains an integer t (1 ≤ t ≤ 200 000), denoting the number of test cases in the input.

For each test case, there's one line with a non-empty string of lowercase Latin letters a.

The total sum of lengths of strings in all test cases is at most 200 000.

Output

For each test case, in the first line, you should print m: the smallest number of steps to make a empty. Each of the following m lines should contain two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ |a|), denoting, that the i-th step is removing the characters from index l_i to r_i in the current string. (indices are numbered starting from 1). 

Note that after the deletion of the substring, indices of remaining characters may change, and r_i should be at most the current length of a.

If there are several possible solutions, you can print any.

Example

Input


4
aabbcc
aaabbb
aaa
abacad


Output


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

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

**_Extra perfect number_** *is the number that* **_first_** and **_last_** *bits* are **_set bits_**.

____

# Task

**_Given_**  *a positive integer*   `N` ,  **_Return_** the **_extra perfect numbers_** *in range from*  `1`  to  `N` .
____

# Warm-up (Highly recommended)

# [Playing With Numbers Series](https://www.codewars.com/collections/playing-with-numbers)
___

# Notes 


* **_Number_** *passed is always*  **_Positive_** .

* **_Returned array/list_** should *contain the extra perfect numbers in ascending order*  **from lowest to highest**
___

# Input >> Output Examples

```
extraPerfect(3)  ==>  return {1,3}
```
## **_Explanation_**:

# (1)10 =(1)2

**First** and **last** bits as **_set bits_**.

# (3)10 = (11)2

**First** and **last** bits as **_set bits_**.
___

```
extraPerfect(7)  ==>  return {1,3,5,7}
```

## **_Explanation_**:

# (5)10 = (101)2

**First** and **last** bits as **_set bits_**.

# (7)10 = (111)2

**First** and **last** bits as **_set bits_**.
___
___
___

# [Playing with Numbers Series](https://www.codewars.com/collections/playing-with-numbers)

# [Playing With Lists/Arrays Series](https://www.codewars.com/collections/playing-with-lists-slash-arrays)

# [For More Enjoyable Katas](http://www.codewars.com/users/MrZizoScream/authored)
___

## ALL translations are welcomed

## Enjoy Learning !!
# Zizou

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's keep the problem statement easy, shall we?
How many integers of length N are such that sum of square of digits in exactly K and they are divisible by M?

Input Format

First line contains three space separated integers : N , M and K.

Output Format

Output the only integer as described in the question. Since the answer can be too big, output it modulo 10^9 + 7.

Constraints

**1 ≤ N ≤ 50

1 ≤ M ≤ 100

1 ≤ K ≤ 2000**

SAMPLE INPUT
2 12 20

SAMPLE OUTPUT
1

Explanation

The only number that satisfies is 24.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $a_1,a_2,\ldots,a_n$. The task is to perform the following queries on it:

Type 1. Given two integers $\boldsymbol{l}$ and $\textbf{r}$ $(1\leq l\lt r\leq n;r-l+1\ is even)$. Reorder the elements of the sequence in such a way (changed part of the sequence is in brackets):
$a_1,a_2,\ldots,a_n\rightarrow a_1,a_2,\ldots,a_{l-2},a_{l-1},\left[a_{l+1},a_l,a_{l+3},a_{l+2},\ldots,a_{r},a_{r-1}\right],a_{r+1},a_{r+2},\ldots,a_{n}$
That is swap the first two elements of segment $[l,r]$, the second two elements, and so on.

Type 2. Given two integers $\boldsymbol{l}$ and $\textbf{r}$, print the value of sum $\sum\limits_{i=l}^{r}a_{i}$.

Input Format  

The first line contains two integers $n$ and $\textit{q}$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, denoting initial sequence.

Each of the next $\textit{q}$ lines contains three integers $tp_i,l_i,r_i$, where $t p_i$ denotes the type of the query, and $l_i,r_i$ are parameters of the query. It's guaranteed that for a first-type query $(r-l+1)$ will be even.  

Constraints 

$2\leq n\leq2\times10^5$ 

$1\leq q\leq2\times10^5$ 

$1\leq a_i\leq10^6$ 

$1\leq t p_i\leq2$ 

$1\leq l_i\leq r_i\leq n$

Output Format

For each query of the second type print the required sum.

Sample Input

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

Example Output

5
7
9

Explanation

After the first query the sequence becomes [1, 3, 2, 5, 4, 6].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of length N.

Determine the count of subarrays of A which contain their length as an element.

Formally, count the number of pairs (L, R) (1≤ L≤ R≤ N) such that: (R-L+1) \in \{A_{L}, A_{L+1}, \ldots, A_{R}\}.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the length of the array A.
- Second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} - denoting the array A.

------ Output Format ------ 

For each test case, output the count of subarrays containing their lengths.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
1 2 1
5
2 3 1 3 5
10
10 7 4 4 2 9 2 1 9 3

----- Sample Output 1 ------ 
4
6
15

----- explanation 1 ------ 
Test Case $1$: There are $4$ subarrays $(i,j)$ containing their lengths. They are $(1,1), (1,2), (2,3),$ and $(3,3)$.

Test Case $2$: There are $6$ subarrays $(i,j)$ containing their lengths. They are $(1,2), (1,3), (1,5), (2, 4), (3,3),$ and $(3,5)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to return the sum of Triangular Numbers up-to-and-including the `nth` Triangular Number.

Triangular Number: "any of the series of numbers (1, 3, 6, 10, 15, etc.) obtained by continued summation of the natural numbers 1, 2, 3, 4, 5, etc."

```
[01]
02 [03]
04 05 [06]
07 08 09 [10]
11 12 13 14 [15]
16 17 18 19 20 [21]
```

e.g. If `4` is given: `1 + 3 + 6 + 10 = 20`.

Triangular Numbers cannot be negative so return 0 if a negative number is given.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given string $s$ of length $n$ consisting of 0-s and 1-s. You build an infinite string $t$ as a concatenation of an infinite number of strings $s$, or $t = ssss \dots$ For example, if $s =$ 10010, then $t =$ 100101001010010...

Calculate the number of prefixes of $t$ with balance equal to $x$. The balance of some string $q$ is equal to $cnt_{0, q} - cnt_{1, q}$, where $cnt_{0, q}$ is the number of occurrences of 0 in $q$, and $cnt_{1, q}$ is the number of occurrences of 1 in $q$. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $2T$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $-10^9 \le x \le 10^9$) — the length of string $s$ and the desired balance, respectively.

The second line contains the binary string $s$ ($|s| = n$, $s_i \in \{\text{0}, \text{1}\}$).

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print the number of prefixes or $-1$ if there is an infinite number of such prefixes.


-----Example-----
Input
4
6 10
010010
5 3
10101
1 0
0
2 0
01

Output
3
0
1
-1



-----Note-----

In the first test case, there are 3 good prefixes of $t$: with length $28$, $30$ and $32$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pavel has several sticks with lengths equal to powers of two.

He has $a_0$ sticks of length $2^0 = 1$, $a_1$ sticks of length $2^1 = 2$, ..., $a_{n-1}$ sticks of length $2^{n-1}$. 

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 300\,000$) — the number of different lengths of sticks.

The second line contains $n$ integers $a_0$, $a_1$, ..., $a_{n-1}$ ($1 \leq a_i \leq 10^9$), where $a_i$ is the number of sticks with the length equal to $2^i$.


-----Output-----

Print a single integer — the maximum possible number of non-degenerate triangles that Pavel can make.


-----Examples-----
Input
5
1 2 2 2 2

Output
3

Input
3
1 1 1

Output
0

Input
3
3 3 3

Output
3



-----Note-----

In the first example, Pavel can, for example, make this set of triangles (the lengths of the sides of the triangles are listed): $(2^0, 2^4, 2^4)$, $(2^1, 2^3, 2^3)$, $(2^1, 2^2, 2^2)$.

In the second example, Pavel cannot make a single triangle.

In the third example, Pavel can, for example, create this set of triangles (the lengths of the sides of the triangles are listed): $(2^0, 2^0, 2^0)$, $(2^1, 2^1, 2^1)$, $(2^2, 2^2, 2^2)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N. You have to check whether every bit in the binary representation of the given number is set or not.
Example 1:
Input:
N = 7
Output:
1
Explanation:
Binary for 7 is 111 all the
bits are set so output is 1
Example 2:
Input:
N = 8
Output:
0
Explanation:
Binary for 8 is 1000 all the
bits are not set so output is 0.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isBitSet() which takes an integer N as input parameters and returns 1 if all the bits in N's binary representation is set or return 0 otherwise.
Expected Time Complexity: O(1)
Expected Space Complexity: O(1)
Constraints:
0<=N<=100000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has n positive integers a_1, a_2, ..., a_{n}. 

His friend Vasya decided to joke and replaced all digits in Petya's numbers with a letters. He used the lowercase letters of the Latin alphabet from 'a' to 'j' and replaced all digits 0 with one letter, all digits 1 with another letter and so on. For any two different digits Vasya used distinct letters from 'a' to 'j'.

Your task is to restore Petya's numbers. The restored numbers should be positive integers without leading zeros. Since there can be multiple ways to do it, determine the minimum possible sum of all Petya's numbers after the restoration. It is guaranteed that before Vasya's joke all Petya's numbers did not have leading zeros.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1 000) — the number of Petya's numbers.

Each of the following lines contains non-empty string s_{i} consisting of lowercase Latin letters from 'a' to 'j' — the Petya's numbers after Vasya's joke. The length of each string does not exceed six characters.


-----Output-----

Determine the minimum sum of all Petya's numbers after the restoration. The restored numbers should be positive integers without leading zeros. It is guaranteed that the correct restore (without leading zeros) exists for all given tests.


-----Examples-----
Input
3
ab
de
aj

Output
47

Input
5
abcdef
ghij
bdef
accbd
g

Output
136542

Input
3
aa
jj
aa

Output
44



-----Note-----

In the first example, you need to replace the letter 'a' with the digit 1, the letter 'b' with the digit 0, the letter 'd' with the digit 2, the letter 'e' with the digit 3, and the letter 'j' with the digit 4. So after the restoration numbers will look like [10, 23, 14]. The sum of them is equal to 47, which is the minimum possible sum of the numbers after the correct restoration.

In the second example the numbers after the restoration can look like: [120468, 3579, 2468, 10024, 3]. 

In the second example the numbers after the restoration can look like: [11, 22, 11].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke found a random number generator. It generates an integer between 0 and N-1 (inclusive). An integer sequence A_0, A_1, \cdots, A_{N-1} represents the probability that each of these integers is generated. The integer i (0 \leq i \leq N-1) is generated with probability A_i / S, where S = \sum_{i=0}^{N-1} A_i. The process of generating an integer is done independently each time the generator is executed.

Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:

* For every i (0 \leq i \leq N-1), the integer i has been generated at least B_i times so far.



Find the expected number of times Snuke will generate an integer, and print it modulo 998244353. More formally, represent the expected number of generations as an irreducible fraction P/Q. Then, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353, so print this R.

From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo 998244353 can be defined.

Constraints

* 1 \leq N \leq 400
* 1 \leq A_i
* \sum_{i=0}^{N-1} A_i \leq 400
* 1 \leq B_i
* \sum_{i=0}^{N-1} B_i \leq 400
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}


Output

Print the expected number of times Snuke will generate an integer, modulo 998244353.

Examples

Input

2
1 1
1 1


Output

3


Input

3
1 3
2 2
3 1


Output

971485877


Input

15
29 3
78 69
19 15
82 14
9 120
14 51
3 7
6 14
28 4
13 12
1 5
32 30
49 24
35 23
2 9


Output

371626143

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str of length N, you have to find number of palindromic subsequence (need not necessarily be distinct) present in the string str.
Note: You have to return the answer module 10^{9}+7;
 
Example 1:
Input: 
Str = "abcd"
Output: 
4
Explanation:
palindromic subsequence are : "a" ,"b", "c" ,"d"
 
Example 2:
Input: 
Str = "aab"
Output: 
4
Explanation:
palindromic subsequence are :"a", "a", "b", "aa"
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPs() which takes a string str as input parameter and returns the number of palindromic subsequence.
 
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N*N)
Constraints:
1<=length of string str <=1000

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