vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Just another day in the world of Minecraft, Steve is getting ready to start his next exciting project -- building a railway system!

![Alt text](http://static.planetminecraft.com/files/resource_media/screenshot/1506/2015-02-02_0156508603066.jpg)

But first, Steve needs to melt some iron ores in the furnace to get the main building blocks of rails -- iron ingots. ![Alt text](http://www.blocksandgold.com/media/catalog/product/cache/3/image/35x/cbcbef48e5e3bcce7c7ed908f20bc5b4/i/r/ironingot_icon32.png)

Each iron ingot takes 11 seconds* to produce. Steve needs a lot of them, and he has the following fuel options to add into the furnace: 

* Buckets of lava, each lasts 800 seconds* ![Alt text](http://www.minecraftguides.org/images/items/bucketL.gif)
* Blaze rod, each lasts 120 seconds ![Alt text](http://www.minecraftguides.org/images/items/blazerod.gif)
* Coals, each lasts 80 seconds ![Alt text](http://www.minecraftguides.org/images/items/coal.gif)
* Blocks of Wood, each lasts 15 seconds ![Alt text](http://www.minecraftguides.org/images/itemGifs/logs.gif)
* Sticks, each lasts 1 second* ![Alt text](http://www.minecraftguides.org/images/items/stick.gif)

In Ruby: 
Write a function `calc_fuel` that calculates the **minimum** amount of fuel needed to produce a certain number of iron ingots. This function should return a hash of the form `{:lava => 2, :blaze_rod => 1, :coal => 1, :wood => 0, :stick => 0}`
In JavaScript:
Write a function `calcFuel` that calculates the **minimum** amount of fuel needed to produce a certain number of iron ingots. This function should return an object of the form `{lava: 2, blazeRod: 1, coal: 1, wood: 0, stick: 0}`
In Python:
Write a function `calc_fuel` that calculates the **minimum** amount of fuel needed to produce a certain number of iron ingots. This function should return a dictionary of the form `{"lava": 2, "blaze rod": 1, "coal": 1, "wood": 0, "stick": 0}`

---
*fictional values

To all the Minecraft players out there: 
feel free to expand this series or let me know if you have any ideas related to Minecraft that can be turned into codewars puzzles. Some ideas I have that might potentially be turned into katas:

* distance traveled in real world vs. in Nether
* shortest path problems related to mining diamonds/gold/goodies that appears in different levels under ground
* growth of animal population from breeding
* redstone stuff?!

If you do end up expanding this series, please send me a link of your kata so I can check it out and include a link to your kata here :-)

* [Minecraft Series #1: Steve wants to build a beacon pyramid](https://www.codewars.com/kata/minecraft-series-number-1-steve-wants-to-build-a-beacon-pyramid/ruby)
* [Minecraft Series #3: Lava is amazing! ](https://www.codewars.com/kata/583a23d40cf946ec380002c2)
* [Minecraft Series #4: Lava is amazing, however...](https://www.codewars.com/kata/583a6b0b171f3a3c3f0003e3)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function f, which is defined as follows:$f(l, r) = \sum_{i = l}^{r - 1}|a [ i ] - a [ i + 1 ]|\cdot(- 1)^{i - l}$

In the above formula, 1 ≤ l < r ≤ n must hold, where n is the size of the Main Uzhlyandian Array a, and |x| means absolute value of x. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of f among all possible values of l and r for the given array a.


-----Input-----

The first line contains single integer n (2 ≤ n ≤ 10^5) — the size of the array a.

The second line contains n integers a_1, a_2, ..., a_{n} (-10^9 ≤ a_{i} ≤ 10^9) — the array elements.


-----Output-----

Print the only integer — the maximum value of f.


-----Examples-----
Input
5
1 4 2 3 1

Output
3
Input
4
1 5 4 7

Output
6


-----Note-----

In the first sample case, the optimal value of f is reached on intervals [1, 2] and [2, 5].

In the second case maximal value of f is reachable only on the whole array.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya bought the collected works of a well-known Berland poet Petya in *n* volumes. The volumes are numbered from 1 to *n*. He thinks that it does not do to arrange the book simply according to their order. Vasya wants to minimize the number of the disposition’s divisors — the positive integers *i* such that for at least one *j* (1<=≤<=*j*<=≤<=*n*) is true both: *j* *mod* *i*<==<=0 and at the same time *p*(*j*) *mod* *i*<==<=0, where *p*(*j*) is the number of the tome that stands on the *j*-th place and *mod* is the operation of taking the division remainder. Naturally, one volume can occupy exactly one place and in one place can stand exactly one volume.

Help Vasya — find the volume disposition with the minimum number of divisors.

Input Specification:
The first line contains number *n* (1<=≤<=*n*<=≤<=100000) which represents the number of volumes and free places.

Output Specification:
Print *n* numbers — the sought disposition with the minimum divisor number. The *j*-th number (1<=≤<=*j*<=≤<=*n*) should be equal to *p*(*j*) — the number of tome that stands on the *j*-th place. If there are several solutions, print any of them.

Demo Input:
['2\n', '3\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vivek has encountered a problem. He has a maze that can be represented as an n × m grid. Each of the grid cells may represent the following:

  * Empty — '.' 
  * Wall — '#' 
  * Good person — 'G' 
  * Bad person — 'B' 



The only escape from the maze is at cell (n, m).

A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through.

Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions.

It is guaranteed that the cell (n,m) is empty. Vivek can also block this cell.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n, m (1 ≤ n, m ≤ 50) — the number of rows and columns in the maze.

Each of the next n lines contain m characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

Output

For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"

You may print every letter in any case (upper or lower).

Example

Input


6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.


Output


Yes
Yes
No
No
Yes
Yes

Note

For the first and second test cases, all conditions are already satisfied.

For the third test case, there is only one empty cell (2,2), and if it is replaced with a wall then the good person at (1,2) will not be able to escape.

For the fourth test case, the good person at (1,1) cannot escape.

For the fifth test case, Vivek can block the cells (2,3) and (2,2).

For the last test case, Vivek can block the destination cell (2, 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don't make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — the number of towns and the number of railways respectively.

Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v).

You may assume that there is at most one railway connecting any two towns.


-----Output-----

Output one integer — the smallest possible time of the later vehicle's arrival in town n. If it's impossible for at least one of the vehicles to reach town n, output  - 1.


-----Examples-----
Input
4 2
1 3
3 4

Output
2

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

Output
-1

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

Output
3



-----Note-----

In the first sample, the train can take the route $1 \rightarrow 3 \rightarrow 4$ and the bus can take the route $1 \rightarrow 2 \rightarrow 4$. Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$\textit{Knight L}$ is a chess piece that moves in an L shape. We define the possible moves of $\textit{Knight L}(a,b)$ as any movement from some position $(x_{1},y_{1})$ to some $(x_2,y_2)$ satisfying either of the following:

$x_2=x_1\pm a$ and $y_2=y_1\pm b$, or  
$x_2=x_1\pm b$ and $y_2=y_1\pm a$  

Note that $(a,b)$ and $(b,a)$ allow for the same exact set of movements. For example, the diagram below depicts the possible locations that $\textit{Knight L}(1,2)$ or $\textit{Knight L}(2,1)$ can move to from its current location at the center of a $5\times5$ chessboard:

Observe that for each possible movement, the Knight moves $2$ units in one direction (i.e., horizontal or vertical) and $\mbox{1}$ unit in the perpendicular direction.

Given the value of $n$ for an $n\times n$ chessboard, answer the following question for each $(a,b)$ pair where $1\leq a,b<n$:

What is the minimum number of moves it takes for $\textit{Knight L}(a,b)$ to get from position $(0,0)$ to position $(n-1,n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each $\textit{Knight L}(a,b)$ according to the Output Format specified below.

Input Format

A single integer denoting $n$.

Constraints

$5\leq n\leq25$

Output Format

Print exactly $n-1$ lines of output in which each line $\boldsymbol{i}$ (where $1\leq i\lt n$) contains $n-1$ space-separated integers describing the minimum number of moves $\textit{Knight L}(i,j)$ must make for each respective $j$ (where $1\leq j\lt n$). If some $\textit{Knight L}(i,j)$ cannot reach position $(n-1,n-1)$, print -1 instead.  

For example, if $n=3$, we organize the answers for all the $(i,j)$ pairs in our output like this:

(1,1) (1,2)
(2,1) (2,2)

Sample Input 0
5

Sample Output 0
4 4 2 8
4 2 4 4
2 4 -1 -1
8 4 -1 1

Explanation 0

The diagram below depicts possible minimal paths for $\textit{Knight L}(1,1)$, $\textit{Knight L}(1,2)$, and $\textit{Knight L}(1,3)$:

One minimal path for $\textit{Knight}L(1,4)$ is: $(0,0)\to(1,4)\to(2,0)\to(3,4)\to(4,0)\to(0,1)\to(4,2)\to(0,3)\to(4,4)$

We then print 4 4 2 8 as our first line of output because $\textit{Knight L}(1,1)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,2)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,3)$ took $2$ moves, and $\textit{Knight}L(1,4)$ took $8$ moves. 

In some of the later rows of output, it's impossible for $\textit{Knight L}(i,j)$ to reach position $(4,4)$. For example, $\textit{Knight L}(3,3)$ can only move back and forth between $(0,0)$ and $(3,3)$ so it will never reach $(4,4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A core idea of several left-wing ideologies is that the wealthiest should *support* the poorest, no matter what and that is exactly what you are called to do using this kata (which, on a side note, was born out of the necessity to redistribute the width of `div`s into a given container).

You will be given two parameters, `population` and `minimum`: your goal is to give to each one according to his own needs (which we assume to be equal to `minimum` for everyone, no matter what), taking from the richest (bigger numbers) first.

For example, assuming a population `[2,3,5,15,75]` and `5` as a minimum, the expected result should be `[5,5,5,15,70]`. Let's punish those filthy capitalists, as we all know that being rich has to be somehow a fault and a shame!

If you happen to have few people as the richest, just take from the ones with the lowest index (the closest to the left, in few words) in the array first, on a 1:1 based heroic proletarian redistribution, until everyone is satisfied.

To clarify this rule, assuming a population `[2,3,5,45,45]` and `5` as `minimum`, the expected result should be `[5,5,5,42,43]`.

If you want to see it in steps, consider removing `minimum` from every member of the population, then iteratively (or recursively) adding 1 to the poorest while removing 1 from the richest. Pick the element most at left if more elements exist with the same level of minimal poverty, as they are certainly even more aligned with the party will than other poor people; similarly, it is ok to take from the richest one on the left first, so they can learn their lesson and be more kind, possibly giving more *gifts* to the inspectors of the State!

In steps:
```
[ 2, 3, 5,45,45] becomes
[-3,-2, 0,40,40] that then becomes
[-2,-2, 0,39,40] that then becomes
[-1,-2, 0,39,39] that then becomes
[-1,-1, 0,38,39] that then becomes
[ 0,-1, 0,38,38] that then becomes
[ 0, 0, 0,37,38] that then finally becomes (adding the minimum again, as no value is no longer under the poverty threshold
[ 5, 5, 5,42,43]
```

If giving `minimum` is unfeasable with the current resources (as it often comes to be the case in socialist communities...), for example if the above starting population had set a goal of giving anyone at least `30`, just return an empty array `[]`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x × x, x3 = x2 × x, x4 = x3 × x, ... , x31 = x30 × x.

The operation of squaring can appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x × x, x3 = x2 × x, x6 = x3 × x3, x7 = x6 × x, x14 = x7 × x7,
x15 = x14 × x, x30 = x15 × x15, x31 = x30 × x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x10 = x8 × x2,
x20 = x10 × x10, x30 = x20 × x10, x31 = x30 × x.

There however is no way to compute x31 with fewer multiplications. Thus this is one of the most eficient ways to compute x31 only by multiplications.

If division is also available, we can find a shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x × x, x4 = x2 × x2, x8 = x4 × x4, x16 = x8 × x8, x32 = x16 × x16,
x31 = x32 ÷ x.

This is one of the most eficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence of operations should be x to a positive integer's power. In other words, x-3, for example, should never appear.



Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Example

Input

1
31
70
91
473
512
811
953
0


Output

0
6
8
9
11
9
13
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a chessboard of size 1 × n. It is guaranteed that n is even. The chessboard is painted like this: "BWBW...BW".

Some cells of the board are occupied by the chess pieces. Each cell contains no more than one chess piece. It is known that the total number of pieces equals to $\frac{n}{2}$.

In one step you can move one of the pieces one cell to the left or to the right. You cannot move pieces beyond the borders of the board. You also cannot move pieces to the cells that are already occupied.

Your task is to place all the pieces in the cells of the same color using the minimum number of moves (all the pieces must occupy only the black cells or only the white cells after all the moves are made).


-----Input-----

The first line of the input contains one integer n (2 ≤ n ≤ 100, n is even) — the size of the chessboard. 

The second line of the input contains $\frac{n}{2}$ integer numbers $p_{1}, p_{2}, \ldots, p_{\frac{n}{2}}$ (1 ≤ p_{i} ≤ n) — initial positions of the pieces. It is guaranteed that all the positions are distinct.


-----Output-----

Print one integer — the minimum number of moves you have to make to place all the pieces in the cells of the same color.


-----Examples-----
Input
6
1 2 6

Output
2

Input
10
1 2 3 4 5

Output
10



-----Note-----

In the first example the only possible strategy is to move the piece at the position 6 to the position 5 and move the piece at the position 2 to the position 3. Notice that if you decide to place the pieces in the white cells the minimum number of moves will be 3.

In the second example the possible strategy is to move $5 \rightarrow 9$ in 4 moves, then $4 \rightarrow 7$ in 3 moves, $3 \rightarrow 5$ in 2 moves and $2 \rightarrow 3$ in 1 move.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots , a_n$ consisting of integers from $0$ to $9$. A subarray $a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r$ is good if the sum of elements of this subarray is equal to the length of this subarray ($\sum\limits_{i=l}^{r} a_i = r - l + 1$).

For example, if $a = [1, 2, 0]$, then there are $3$ good subarrays: $a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0]$ and $a_{1 \dots 3} = [1, 2, 0]$.

Calculate the number of good subarrays of the array $a$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains a string consisting of $n$ decimal digits, where the $i$-th digit is equal to the value of $a_i$.

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


-----Output-----

For each test case print one integer — the number of good subarrays of the array $a$.


-----Example-----
Input
3
3
120
5
11011
6
600005

Output
3
6
1



-----Note-----

The first test case is considered in the statement.

In the second test case, there are $6$ good subarrays: $a_{1 \dots 1}$, $a_{2 \dots 2}$, $a_{1 \dots 2}$, $a_{4 \dots 4}$, $a_{5 \dots 5}$ and $a_{4 \dots 5}$. 

In the third test case there is only one good subarray: $a_{2 \dots 6}$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pasha got a very beautiful string *s* for his birthday, the string consists of lowercase Latin letters. The letters in the string are numbered from 1 to |*s*| from left to right, where |*s*| is the length of the given string.

Pasha didn't like his present very much so he decided to change it. After his birthday Pasha spent *m* days performing the following transformations on his string — each day he chose integer *a**i* and reversed a piece of string (a segment) from position *a**i* to position |*s*|<=-<=*a**i*<=+<=1. It is guaranteed that 2·*a**i*<=≤<=|*s*|.

You face the following task: determine what Pasha's string will look like after *m* days.

Input Specification:
The first line of the input contains Pasha's string *s* of length from 2 to 2·105 characters, consisting of lowercase Latin letters.

The second line contains a single integer *m* (1<=≤<=*m*<=≤<=105) —  the number of days when Pasha changed his string.

The third line contains *m* space-separated elements *a**i* (1<=≤<=*a**i*; 2·*a**i*<=≤<=|*s*|) — the position from which Pasha started transforming the string on the *i*-th day.

Output Specification:
In the first line of the output print what Pasha's string *s* will look like after *m* days.

Demo Input:
['abcdef\n1\n2\n', 'vwxyz\n2\n2 2\n', 'abcdef\n3\n1 2 3\n']

Demo Output:
['aedcbf\n', 'vwxyz\n', 'fbdcea\n']

Note:
none

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