vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает a_{i} страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.

Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Входные данные-----

В первой строке входных данных следуют три целых числа n, x и y (1 ≤ n ≤ 200 000, 0 ≤ x, y ≤ 10^9) — количество команд, количество листов бумаги с двумя чистыми сторонами и количество листов бумаги с одной чистой стороной.

Во второй строке входных данных следует последовательность из n целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10 000), где i-е число равно количеству страниц в комплекте задач для i-й команды.


-----Выходные данные-----

Выведите единственное целое число — максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Примеры-----
Входные данные
2 3 5
4 6

Выходные данные
2

Входные данные
2 3 5
4 7

Выходные данные
2

Входные данные
6 3 5
12 11 12 11 12 11

Выходные данные
1



-----Примечание-----

В первом тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать весь первый комплект задач на листах с одной чистой стороной (после этого останется 3 листа с двумя чистыми сторонами и 1 лист с одной чистой стороной), а второй комплект напечатать на трех листах с двумя чистыми сторонами.

Во втором тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать первый комплект задач на двух листах с двумя чистыми сторонами (после этого останется 1 лист с двумя чистыми сторонами и 5 листов с одной чистой стороной), а второй комплект напечатать на одном листе с двумя чистыми сторонами и на пяти листах с одной чистой стороной. Таким образом, тренер использует все листы для печати.

В третьем тестовом примере можно напечатать только один комплект задач (любой из трёх 11-страничных). Для печати 11-страничного комплекта задач будет израсходована вся бумага.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A tennis tournament with n participants is running. The participants are playing by an olympic system, so the winners move on and the losers drop out.

The tournament takes place in the following way (below, m is the number of the participants of the current round):  let k be the maximal power of the number 2 such that k ≤ m,  k participants compete in the current round and a half of them passes to the next round, the other m - k participants pass to the next round directly,  when only one participant remains, the tournament finishes. 

Each match requires b bottles of water for each participant and one bottle for the judge. Besides p towels are given to each participant for the whole tournament.

Find the number of bottles and towels needed for the tournament.

Note that it's a tennis tournament so in each match two participants compete (one of them will win and the other will lose).


-----Input-----

The only line contains three integers n, b, p (1 ≤ n, b, p ≤ 500) — the number of participants and the parameters described in the problem statement.


-----Output-----

Print two integers x and y — the number of bottles and towels need for the tournament.


-----Examples-----
Input
5 2 3

Output
20 15

Input
8 2 4

Output
35 32



-----Note-----

In the first example will be three rounds:  in the first round will be two matches and for each match 5 bottles of water are needed (two for each of the participants and one for the judge),  in the second round will be only one match, so we need another 5 bottles of water,  in the third round will also be only one match, so we need another 5 bottles of water. 

So in total we need 20 bottles of water.

In the second example no participant will move on to some round directly.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When we attended middle school were asked to simplify mathematical expressions like "3x-yx+2xy-x" (or usually bigger), and that was easy-peasy ("2x+xy"). But tell that to your pc and we'll see! 

Write a function: `simplify`, that takes a string in input, representing a *multilinear non-constant polynomial in integers coefficients* (like `"3x-zx+2xy-x"`), and returns another string as output where the same expression has been simplified in the following way ( `->` means application of `simplify`):

- All possible sums and subtraction of equivalent monomials ("xy==yx") has been done, e.g.: `"cb+cba" -> "bc+abc"`, `"2xy-yx" -> "xy"`, `"-a+5ab+3a-c-2a" -> "-c+5ab"`

- All monomials appears in order of increasing number of variables, e.g.: `"-abc+3a+2ac" -> "3a+2ac-abc"`, `"xyz-xz" -> "-xz+xyz"`
 
- If two monomials have the same number of variables, they appears in lexicographic order, e.g.: `"a+ca-ab" -> "a-ab+ac"`, `"xzy+zby" ->"byz+xyz"`
  
- There is no leading `+` sign if the first coefficient is positive, e.g.: `"-y+x" -> "x-y"`, but no restrictions for `-`:  `"y-x" ->"-x+y"`

---

__N.B.__ to keep it simplest, the string in input is restricted to represent only *multilinear non-constant polynomials*, so you won't find something like `-3+yx^2'. **Multilinear** means in this context: **of degree 1 on each variable**.

**Warning**: the string in input can contain arbitrary variables represented by lowercase characters in the english alphabet.

__Good Work :)__

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given n, l and r find the number of distinct geometrical progression, each of which contains n distinct integers not less than l and not greater than r. In other words, for each progression the following must hold: l ≤ ai ≤ r and ai ≠ aj , where a1, a2, ..., an is the geometrical progression, 1 ≤ i, j ≤ n and i ≠ j.

Geometrical progression is a sequence of numbers a1, a2, ..., an where each term after first is found by multiplying the previous one by a fixed non-zero number d called the common ratio. Note that in our task d may be non-integer. For example in progression 4, 6, 9, common ratio is <image>.

Two progressions a1, a2, ..., an and b1, b2, ..., bn are considered different, if there is such i (1 ≤ i ≤ n) that ai ≠ bi.

Input

The first and the only line cotains three integers n, l and r (1 ≤ n ≤ 107, 1 ≤ l ≤ r ≤ 107).

Output

Print the integer K — is the answer to the problem.

Examples

Input

1 1 10


Output

10

Input

2 6 9


Output

12

Input

3 1 10


Output

8

Input

3 3 10


Output

2

Note

These are possible progressions for the first test of examples: 

  * 1; 
  * 2; 
  * 3; 
  * 4; 
  * 5; 
  * 6; 
  * 7; 
  * 8; 
  * 9; 
  * 10. 



These are possible progressions for the second test of examples: 

  * 6, 7; 
  * 6, 8; 
  * 6, 9; 
  * 7, 6; 
  * 7, 8; 
  * 7, 9; 
  * 8, 6; 
  * 8, 7; 
  * 8, 9; 
  * 9, 6; 
  * 9, 7; 
  * 9, 8. 



These are possible progressions for the third test of examples: 

  * 1, 2, 4; 
  * 1, 3, 9; 
  * 2, 4, 8; 
  * 4, 2, 1; 
  * 4, 6, 9; 
  * 8, 4, 2; 
  * 9, 3, 1; 
  * 9, 6, 4. 



These are possible progressions for the fourth test of examples: 

  * 4, 6, 9; 
  * 9, 6, 4. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You like playing chess tournaments online.

In your last tournament you played $n$ games. For the sake of this problem, each chess game is either won or lost (no draws). When you lose a game you get $0$ points. When you win you get $1$ or $2$ points: if you have won also the previous game you get $2$ points, otherwise you get $1$ point. If you win the very first game of the tournament you get $1$ point (since there is not a "previous game").

The outcomes of the $n$ games are represented by a string $s$ of length $n$: the $i$-th character of $s$ is W if you have won the $i$-th game, while it is L if you have lost the $i$-th game.

After the tournament, you notice a bug on the website that allows you to change the outcome of at most $k$ of your games (meaning that at most $k$ times you can change some symbol L to W, or W to L). Since your only goal is to improve your chess rating, you decide to cheat and use the bug.

Compute the maximum score you can get by cheating in the optimal way.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t \le 20,000$) — the number of test cases. The description of the test cases follows.

The first line of each testcase contains two integers $n, k$ ($1\le n\le 100,000$, $0\le k\le n$) – the number of games played and the number of outcomes that you can change.

The second line contains a string $s$ of length $n$ containing only the characters W and L. If you have won the $i$-th game then $s_i=\,$W, if you have lost the $i$-th game then $s_i=\,$L.

It is guaranteed that the sum of $n$ over all testcases does not exceed $200,000$.


-----Output-----

For each testcase, print a single integer – the maximum score you can get by cheating in the optimal way.


-----Example-----
Input
8
5 2
WLWLL
6 5
LLLWWL
7 1
LWLWLWL
15 5
WWWLLLWWWLLLWWW
40 7
LLWLWLWWWLWLLWLWWWLWLLWLLWLLLLWLLWWWLWWL
1 0
L
1 1
L
6 1
WLLWLW

Output
7
11
6
26
46
0
1
6



-----Note-----

Explanation of the first testcase. Before changing any outcome, the score is $2$. Indeed, you won the first game, so you got $1$ point, and you won also the third, so you got another $1$ point (and not $2$ because you lost the second game).

An optimal way to cheat is to change the outcomes of the second and fourth game. Doing so, you end up winning the first four games (the string of the outcomes becomes WWWWL). Hence, the new score is $7=1+2+2+2$: $1$ point for the first game and $2$ points for the second, third and fourth game.

Explanation of the second testcase. Before changing any outcome, the score is $3$. Indeed, you won the fourth game, so you got $1$ point, and you won also the fifth game, so you got $2$ more points (since you won also the previous game).

An optimal way to cheat is to change the outcomes of the first, second, third and sixth game. Doing so, you end up winning all games (the string of the outcomes becomes WWWWWW). Hence, the new score is $11 = 1+2+2+2+2+2$: $1$ point for the first game and $2$ points for all the other games.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function, `gooseFilter` / `goose-filter` / `goose_filter` /` GooseFilter`, that takes an array of strings as an argument and returns a filtered array containing the same elements but with the 'geese' removed.

The geese are any strings in the following array, which is pre-populated in your solution:

```python
geese = ["African", "Roman Tufted", "Toulouse", "Pilgrim", "Steinbacher"]
```

For example, if this array were passed as an argument:

```python
["Mallard", "Hook Bill", "African", "Crested", "Pilgrim", "Toulouse", "Blue Swedish"]
```

Your function would return the following array:

```python
["Mallard", "Hook Bill", "Crested", "Blue Swedish"]
```

The elements in the returned array should be in the same order as in the initial array passed to your function, albeit with the 'geese' removed. Note that all of the strings will be in the same case as those provided, and some elements may be repeated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The police department of your city has just started its journey. Initially, they don’t have any manpower. So, they started hiring new recruits in groups.

Meanwhile, crimes keeps occurring within the city. One member of the police force can investigate only one crime during his/her lifetime.

If there is no police officer free (isn't busy with crime) during the occurrence of a crime, it will go untreated.

Given the chronological order of crime occurrences and recruit hirings, find the number of crimes which will go untreated.


-----Input-----

The first line of input will contain an integer n (1 ≤ n ≤ 10^5), the number of events. The next line will contain n space-separated integers.

If the integer is -1 then it means a crime has occurred. Otherwise, the integer will be positive, the number of officers recruited together at that time. No more than 10 officers will be recruited at a time.


-----Output-----

Print a single integer, the number of crimes which will go untreated.


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

Output
2

Input
8
1 -1 1 -1 -1 1 1 1

Output
1

Input
11
-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1

Output
8



-----Note-----

Lets consider the second example:  Firstly one person is hired.  Then crime appears, the last hired person will investigate this crime.  One more person is hired.  One more crime appears, the last hired person will investigate this crime.  Crime appears. There is no free policeman at the time, so this crime will go untreated.  One more person is hired.  One more person is hired.  One more person is hired. 

The answer is one, as one crime (on step 5) will go untreated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider some positive integer x. Its prime factorization will be of form x = 2^{k_1} ⋅ 3^{k_2} ⋅ 5^{k_3} ⋅ ...

Let's call x elegant if the greatest common divisor of the sequence k_1, k_2, ... is equal to 1. For example, numbers 5 = 5^1, 12 = 2^2 ⋅ 3, 72 = 2^3 ⋅ 3^2 are elegant and numbers 8 = 2^3 (GCD = 3), 2500 = 2^2 ⋅ 5^4 (GCD = 2) are not.

Count the number of elegant integers from 2 to n.

Each testcase contains several values of n, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^5) — the number of values of n in the testcase.

Each of the next T lines contains a single integer n_i (2 ≤ n_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of elegant numbers from 2 to n_i.

Example

Input

4
4
2
72
10


Output

2
1
61
6

Note

Here is the list of non-elegant numbers up to 10:

  * 4 = 2^2, GCD = 2; 
  * 8 = 2^3, GCD = 3; 
  * 9 = 3^2, GCD = 2. 



The rest have GCD = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.



Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.




Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Vietnamese High School graduation exam is in progress! For most Vietnamese high school students, this is their most important exam, as its result not only decides whether they can graduate from high school, but is also used for their university applications.

Today, Hanh finished his final exam, Math, which is Hanh’s strongest subject. In this exam, there are $n$ questions, numbered from $1$ to $n$. Each one is a multiple choice question, with $4$ answers, $A$, $B$, $C$, and $D$. The students have to write the answers on an answer sheet with $n$ lines, the $i$-th line should contain the answer for the $i$-th question. Each question has only one correct answer, and the student will receive one point if their answer matches the correct one.

Hanh started checking his results with his friends confidently. After few minutes, Hanh’s confidence turned into fright: Most of Hanh’s answers are different from his friends’.

Hanh quickly realized that he made a terrible mistake: Hanh wrote the answer for the $2$nd question on the $1$st line of the answer sheet, the answer for the $3$rd question on the $2$nd line, the answer for the $4$th question on the $3$rd line, and so on. Hanh left the $n$-th line of the answer sheet empty, and did not write the answer for the $1$st question anywhere!

Please help Hanh check what will be his final score. Given that Hanh is a great Math student, his answers for all $n$ questions would be correct if they were on the correct line of the answer sheet.

-----Input-----
 - The first line of the input contains a single integer $n$ $(1 \le n \le 1000)$ — the number of questions.
 - $n$ lines follow, the $i$-th line contains a single character, $A$, $B$, $C$, or $D$ — the correct answer for the $i$-th question.

-----Output-----
Print a single integer — Hanh’s final score.

-----Explanation of the first sample input-----
Fortunately for Hanh, all $4$ questions have $A$ as correct answer. So Hanh wrote $A$ on the first three lines, and left the $4$-th line empty. Hanh’s final score is $3$.

-----Examples-----
Sample Input:
4
A
A
A
A
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose you have a special x-y-counter. This counter can store some value as a decimal number; at first, the counter has value 0. 

The counter performs the following algorithm: it prints its lowest digit and, after that, adds either x or y to its value. So all sequences this counter generates are starting from 0. For example, a 4-2-counter can act as follows:

  1. it prints 0, and adds 4 to its value, so the current value is 4, and the output is 0; 
  2. it prints 4, and adds 4 to its value, so the current value is 8, and the output is 04; 
  3. it prints 8, and adds 4 to its value, so the current value is 12, and the output is 048; 
  4. it prints 2, and adds 2 to its value, so the current value is 14, and the output is 0482; 
  5. it prints 4, and adds 4 to its value, so the current value is 18, and the output is 04824. 



This is only one of the possible outputs; for example, the same counter could generate 0246802468024 as the output, if we chose to add 2 during each step.

You wrote down a printed sequence from one of such x-y-counters. But the sequence was corrupted and several elements from the sequence could be erased.

Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string s — the remaining data of the sequence. 

For all 0 ≤ x, y < 10, calculate the minimum number of digits you have to insert in the string s to make it a possible output of the x-y-counter. Note that you can't change the order of digits in string s or erase any of them; only insertions are allowed.

Input

The first line contains a single string s (1 ≤ |s| ≤ 2 ⋅ 10^6, s_i ∈ \{0 - 9\}) — the remaining data you have. It's guaranteed that s_1 = 0.

Output

Print a 10 × 10 matrix, where the j-th integer (0-indexed) on the i-th line (0-indexed too) is equal to the minimum number of digits you have to insert in the string s to make it a possible output of the i-j-counter, or -1 if there is no way to do so.

Example

Input


0840


Output


-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7 

Note

Let's take, for example, 4-3-counter. One of the possible outcomes the counter could print is 0(4)8(1)4(7)0 (lost elements are in the brackets).

One of the possible outcomes a 2-3-counter could print is 0(35)8(1)4(7)0.

The 6-8-counter could print exactly the string 0840.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bracket sequence consisting of ‘(’ and ‘)’ is defined to be valid as follows: 
 - An empty sequence is valid.
 - If $X$ is a valid bracket sequence, then $(X)$ is a valid bracket sequence.
 - If $X$ and $Y$ are valid bracket sequences, then the concatenation of $X$ and $Y$, $Z=XY$, is a valid bracket sequence.

For example, “(())”, “()()”, and “(()())()” are all valid bracket sequences, while “(” and “())” are invalid bracket sequences.

You get a bracket sequence from the professor of length $n$. However, it might not be valid at the moment. The professor asks you to check if it is possible to make the sequence valid by performing at most one segment inversion operation. That is, you may choose two 1-based indices $l$ and $r$ ($1~ \leq ~ l~ \leq ~ r~ \leq ~ n$) and invert each bracket with an index in the closed interval $[l,r]$. After the inversion, a left bracket ‘(’ becomes a right bracket ‘)’, and a right bracket ‘)’ becomes a left bracket ‘(’.

You can make “())(” valid by inverting the segment $[3,4]$. You can make “()))” valid by inverting the segment $[3,3]$, or alternatively by inverting the segment $[2,2]$. However, there does not exist a segment you can invert to make “)))(” valid.

-----Input-----
The input consists of one line containing between $1$ and $5000$ brackets.

-----Output-----
Output “possible” if you can make the bracket sequence valid by performing at most one segment inversion, or “impossible” otherwise.

-----Examples-----
Sample Input 1:
()))
Sample Output 1:
possible

Sample Input 2:
)))(
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: One-Based Arithmetic

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Prof. Vasechkin wants to represent positive integer *n* as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=&lt;<=1015).

Output Specification:
Print expected minimal number of digits 1.

Demo Input:
['121\n']

Demo Output:
['6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
VK news recommendation system daily selects interesting publications of one of $n$ disjoint categories for each user. Each publication belongs to exactly one category. For each category $i$ batch algorithm selects $a_i$ publications.

The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of $i$-th category within $t_i$ seconds. 

What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm.


-----Input-----

The first line of input consists of single integer $n$ — the number of news categories ($1 \le n \le 200\,000$).

The second line of input consists of $n$ integers $a_i$ — the number of publications of $i$-th category selected by the batch algorithm ($1 \le a_i \le 10^9$).

The third line of input consists of $n$ integers $t_i$ — time it takes for targeted algorithm to find one new publication of category $i$ ($1 \le t_i \le 10^5)$.


-----Output-----

Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.


-----Examples-----
Input
5
3 7 9 7 8
5 2 5 7 5

Output
6

Input
5
1 2 3 4 5
1 1 1 1 1

Output
0



-----Note-----

In the first example, it is possible to find three publications of the second type, which will take 6 seconds.

In the second example, all news categories contain a different number of publications.

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