vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Inna loves sleeping very much, so she needs n alarm clocks in total to wake up. Let's suppose that Inna's room is a 100 × 100 square with the lower left corner at point (0, 0) and with the upper right corner at point (100, 100). Then the alarm clocks are points with integer coordinates in this square.

The morning has come. All n alarm clocks in Inna's room are ringing, so Inna wants to turn them off. For that Inna has come up with an amusing game:  First Inna chooses a type of segments that she will use throughout the game. The segments can be either vertical or horizontal.  Then Inna makes multiple moves. In a single move, Inna can paint a segment of any length on the plane, she chooses its type at the beginning of the game (either vertical or horizontal), then all alarm clocks that are on this segment switch off. The game ends when all the alarm clocks are switched off. 

Inna is very sleepy, so she wants to get through the alarm clocks as soon as possible. Help her, find the minimum number of moves in the game that she needs to turn off all the alarm clocks!


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the number of the alarm clocks. The next n lines describe the clocks: the i-th line contains two integers x_{i}, y_{i} — the coordinates of the i-th alarm clock (0 ≤ x_{i}, y_{i} ≤ 100).

Note that a single point in the room can contain any number of alarm clocks and the alarm clocks can lie on the sides of the square that represents the room.


-----Output-----

In a single line print a single integer — the minimum number of segments Inna will have to draw if she acts optimally.


-----Examples-----
Input
4
0 0
0 1
0 2
1 0

Output
2

Input
4
0 0
0 1
1 0
1 1

Output
2

Input
4
1 1
1 2
2 3
3 3

Output
3



-----Note-----

In the first sample, Inna first chooses type "vertical segments", and then she makes segments with ends at : (0, 0), (0, 2); and, for example, (1, 0), (1, 1). If she paints horizontal segments, she will need at least 3 segments.

In the third sample it is important to note that Inna doesn't have the right to change the type of the segments during the game. That's why she will need 3 horizontal or 3 vertical segments to end the game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider $n$ initial strings of lower case letters, where no initial string is a prefix of any other initial string. Now, consider choosing $k$ of the strings (no string more than once), and concatenating them together. You can make this many such composite strings:$n \times (n-1) \times (n-2) \times \ldots \times (n-k+1)$

Consider sorting all of the composite strings you can get via this process in alphabetical order. You are given a test composite string, which is guaranteed to belong on this list. Find the position of this test composite string in the alphabetized list of all composite strings, modulo $10^9+7$. The first composite string in the list is at position $1$.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers, first $n$ and then $k$ ($1 \le k \le n$), where $n$ is the number of initial strings, and $k$ is the number of initial strings you choose to form composite strings. The upper bounds of $n$ and $k$ are limited by the constraints on the strings, in the following paragraphs.

Each of the next $n$ lines will contain a string, which will consist of one or more lower case letters $a..z$. These are the $n$ initial strings. It is guaranteed that none of the initial strings will be a prefix of any other of the initial strings.

Finally, the last line will contain another string, consisting of only lower case letters $a..z$. This is the test composite string, the position of which in the sorted list you must find. This test composite string is guaranteed to be a concatenation of $k$ unique initial strings.

The sum of the lengths of all input strings, including the test string, will not exceed $10^6$ letters.

-----Output-----
Output a single integer, which is the position in the list of sorted composite strings where the test composite string occurs. Output this number modulo $10^9+7$.

-----Examples-----
Sample Input:
5 3
a
b
c
d
e
cad
Sample Output:
26

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The blinds are known to consist of opaque horizontal stripes that can be rotated thus regulating the amount of light flowing in the room. There are *n* blind stripes with the width of 1 in the factory warehouse for blind production. The problem is that all of them are spare details from different orders, that is, they may not have the same length (it is even possible for them to have different lengths)

Every stripe can be cut into two or more parts. The cuttings are made perpendicularly to the side along which the length is measured. Thus the cuttings do not change the width of a stripe but each of the resulting pieces has a lesser length (the sum of which is equal to the length of the initial stripe)

After all the cuttings the blinds are constructed through consecutive joining of several parts, similar in length, along sides, along which length is measured. Also, apart from the resulting pieces an initial stripe can be used as a blind if it hasn't been cut. It is forbidden to construct blinds in any other way.

Thus, if the blinds consist of *k* pieces each *d* in length, then they are of form of a rectangle of *k*<=×<=*d* bourlemeters. 

Your task is to find for what window possessing the largest possible area the blinds can be made from the given stripes if on technical grounds it is forbidden to use pieces shorter than *l* bourlemeter. The window is of form of a rectangle with side lengths as positive integers.

Input Specification:
The first output line contains two space-separated integers *n* and *l* (1<=≤<=*n*,<=*l*<=≤<=100). They are the number of stripes in the warehouse and the minimal acceptable length of a blind stripe in bourlemeters. The second line contains space-separated *n* integers *a**i*. They are the lengths of initial stripes in bourlemeters (1<=≤<=*a**i*<=≤<=100).

Output Specification:
Print the single number — the maximal area of the window in square bourlemeters that can be completely covered. If no window with a positive area that can be covered completely without breaking any of the given rules exist, then print the single number 0.

Demo Input:
['4 2\n1 2 3 4\n', '5 3\n5 5 7 3 1\n', '2 3\n1 2\n']

Demo Output:
['8\n', '15\n', '0\n']

Note:
In the first sample test the required window is 2 × 4 in size and the blinds for it consist of 4 parts, each 2 bourlemeters long. One of the parts is the initial stripe with the length of 2, the other one is a part of a cut stripe with the length of 3 and the two remaining stripes are parts of a stripe with the length of 4 cut in halves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tech Families are an integral part of life @ VNIT. Dewang has quiet a few tech sons and daughters. His tech family is such that every person in his family can be represented by N relations.
A regular relation looks like this - /son1/son2/son3
/ operator is used here as the son of/daughter of operator.
The first / operator implies that the ultimate parent is Dewang. And so there is no need to mention his name in the relation. But Dewang is not satisfied with his small family. So now Dewang with his sons and daughters plan to increase their family tree. So they take interviews from first years for those who are worthy. After the interview they think of M relations that they want to implement. After such a long meeting Dewang is exhausted but he needs to find out how many adoptions are to be made so that all of the adoption relations are satisfied. Help Dewang count the number of adoptions.

NOTE: Adoption schemes are such that there might be some first year who will be adopting first years.

INPUT 

First line of the Input file has an integer T which is the number of test cases. First line of each test case contains 2 integers N and M. Next N line contains all the relations that already exist in his tech family. Next M line contains M relations that are to be made.

OUTPUT 

For every test case output a single integer which gives the value of adoptions that are to be made.

LIMITS

Every name in the relation follows the regular expression :[a-z0-9]

SAMPLE INPUT
2
0 2
/neha/shreya/anushree
/neha/shreya/shubham
2 1
/yogeshree
/yogeshree/radhika
/yogeshree

SAMPLE OUTPUT
4
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Coconut Splat is one of Theta’s favorite counting-out games. It goes like this: initially, all players stand in a circle with their hands folded together (like an intact coconut). In clockwise order, one player touches the hands of the other players and says the rhyme: “Co-co-nut, Co-co-nut, Co-co-nut, Splat!” At each syllable, the player touches a hand, and the player whose hand or hands is touched last takes one of the following actions:
 - If the player’s hands are still folded, they are split into two fists (the coconut is cracked in two halves). The next round starts with the fist that is the first half of the coconut, then the second half, then going to the next player.
 - If a fist is touched last, the hand is turned palm down (the milk spills out). The next round starts with the next hand in clockwise order, which could be the other hand of the same player, or it could be the hand or folded hands belonging to the next player.
 - If a hand that is already turned palm down is touched last, the player to whom it belongs puts the hand behind their back and this hand won’t be counted in the following rounds. The next round starts with the next hand in clockwise order as in the previous case.
 - If a player has put both of their hands behind their back, that player is out of the game. The game ends when there is only one player left.

The hand or hands of the player doing the counting are taken into account (for instance, the counting player touches their thigh when it would be her turn to be touched).

There are variations of this game, for instance, some kids say “Coconut, coconut, crack your nut!” instead, which has only $9$ instead of $10$ syllables as in the “Co-co-nut, Co-co-nut, Co-co-nut, Splat!” rhyme.

There are $n$ players, and counting always starts with the folded hands of player $1$. For instance, in the first round, if the rhyme has $3$ syllables, player $3$ would be the one to first crack their coconut into two fists.

Write a program that determines the winner of the counting-out game based on the number of players and based on the number of syllables in the rhyme that is used!

-----Input-----
The input consists of a single test case with two numbers $s$ ($0 < s \le 100$) and $n$ ($2 \le n \le 100$) denoting the number of syllables in the rhyme and the number of players, respectively.

-----Output-----
Output a single integer $p$ ($1 \le p \le n$), the number of the player who is left.

-----Examples-----
Sample Input 1:
10 2
Sample Output 1:
2

Sample Input 2:
10 10
Sample Output 2:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a special offer in Vasya's favourite supermarket: if the customer buys $a$ chocolate bars, he or she may take $b$ additional bars for free. This special offer can be used any number of times.

Vasya currently has $s$ roubles, and he wants to get as many chocolate bars for free. Each chocolate bar costs $c$ roubles. Help Vasya to calculate the maximum possible number of chocolate bars he can get!


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of testcases.

Each of the next $t$ lines contains four integers $s, a, b, c~(1 \le s, a, b, c \le 10^9)$ — the number of roubles Vasya has, the number of chocolate bars you have to buy to use the special offer, the number of bars you get for free, and the cost of one bar, respectively.


-----Output-----

Print $t$ lines. $i$-th line should contain the maximum possible number of chocolate bars Vasya can get in $i$-th test.


-----Example-----
Input
2
10 3 1 1
1000000000 1 1000000000 1

Output
13
1000000001000000000



-----Note-----

In the first test of the example Vasya can buy $9$ bars, get $3$ for free, buy another bar, and so he will get $13$ bars.

In the second test Vasya buys $1000000000$ bars and gets $1000000000000000000$ for free. So he has $1000000001000000000$ bars.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I have a lot of friends. Every friend is very small.
I often go out with my friends. Put some friends in your backpack and go out together.
Every morning I decide which friends to go out with that day. Put friends one by one in an empty backpack.
I'm not very strong. Therefore, there is a limit to the weight of friends that can be carried at the same time.
I keep friends so that I don't exceed the weight limit. The order in which you put them in depends on your mood.
I won't stop as long as I still have friends to put in. I will never stop.


…… By the way, how many patterns are there in total for the combination of friends in the backpack?



Input

N W
w1
w2
..
..
..
wn


On the first line of input, the integer N (1 ≤ N ≤ 200) and the integer W (1 ≤ W ≤ 10,000) are written in this order, separated by blanks. The integer N represents the number of friends, and the integer W represents the limit of the weight that can be carried at the same time. It cannot be carried if the total weight is greater than W.

The next N lines contain an integer that represents the weight of the friend. The integer wi (1 ≤ wi ≤ 10,000) represents the weight of the i-th friend.

Output

How many possible combinations of friends are finally in the backpack? Divide the total number by 1,000,000,007 and output the remainder. Note that 1,000,000,007 are prime numbers.

Note that "no one is in the backpack" is counted as one.

Examples

Input

4 8
1
2
7
9


Output

2


Input

4 25
20
15
20
15


Output

4


Input

6 37
5
9
13
18
26
33


Output

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A numeric string, $s$, is beautiful if it can be split into a sequence of two or more positive integers, $a[1],a[2],...,a[n]$, satisfying the following conditions:

$a[i]-a[i-1]=1$ for any $1<i\leq n$ (i.e., each element in the sequence is $1$ more than the previous element).
No $a[i]$ contains a leading zero. For example, we can split $s=10203$ into the sequence $\{1,02,03\}$, but it is not beautiful because $02$ and $03$ have leading zeroes.
The contents of the sequence cannot be rearranged. For example, we can split $s=312$ into the sequence $\{3,1,2\}$, but it is not beautiful because it breaks our first constraint (i.e., $1-3\neq1$).

The diagram below depicts some beautiful strings:

Perform $q$ queries where each query consists of some integer string $s$. For each query, print whether or not the string is beautiful on a new line. If it is beautiful, print YES x, where $x$ is the first number of the increasing sequence.  If there are multiple such values of $x$, choose the smallest.  Otherwise, print NO.  

Function Description  

Complete the separateNumbers function in the editor below.  

separateNumbers has the following parameter:  

s: an integer value represented as a string   

Prints 

- string:  Print a string as described above. Return nothing.  

Input Format

The first line contains an integer $q$, the number of strings to evaluate. 

Each of the next $q$ lines contains an integer string $s$ to query.

Constraints

$1\leq q\leq10$
$1\leq|s|\leq32$
$s[i]\in[0-9]$

Sample Input 0
7
1234
91011
99100
101103
010203
13
1

Sample Output 0
YES 1
YES 9
YES 99
NO
NO
NO
NO

Explanation 0

The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For $s=101103$, all possible splits violate the first and/or second conditions.
For $s=010203$, it starts with a zero so all possible splits violate the second condition.
For $s=13$, the only possible split is $\{1,3\}$, which violates the first condition.
For $s=1$, there are no possible splits because $s$ only has one digit.

Sample Input 1
4
99910001001
7891011
9899100
999100010001

Sample Output 1
YES 999
YES 7
YES 98
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tanya likes cartoons. She knows that n new cartoons will be released in his favorite cinema: the i-th of them will be airing from the day a_i to the day b_i (1 ≤ a_i ≤ b_i ≤ 10^9).

The cinema has a special offer: there is a huge discount every day when only one cartoon is airing.

Tanya doesn't care which cartoon she will watch but she'd like to save some money. That's why she asks you to find any day x when only one cartoon will be airing. Formally: find x such that there is exactly one i (1 ≤ i ≤ n) with a_i ≤ x ≤ b_i. If there are several possible answers, print any of them. If there is no such day, print -1.

Input

The first line contains single integer t (1 ≤ t ≤ 1000) — the number of test cases. The following are descriptions of the t test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2000) — the number of cartoons.

In the next n lines, the cartoons themselves are described, one per line, by a pair of integers a_i, b_i (1 ≤ a_i ≤ b_i ≤ 10^9) — the first and last airing days for the i-th cartoon.

It is guaranteed that the sum of the values n for all test cases in the input does not exceed 2000.

Output

Print t answers to given test cases in the order in which they appear in the input: the i-th answer is such x, that only one cartoon will be airing on day x or -1 if there are no such days.

Example

Input


5
1
1 1
3
2 1000000000
2 500000000
500000002 1000000000
3
1 2
3 4
1 4
2
4 11
4 9
3
1 5
10 10
1 5


Output


1
500000001
-1
10
10

Note

In the third test case: at day 1 and 2, first and third cartoons will be airing, and days 3 and 4, second and third cartoons will be airing. So, there is no day when only one cartoon will be airing.

In the fourth test case, 11 is also a possible answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you remember how Kai constructed the word "eternity" using pieces of ice as components?

Little Sheldon plays with pieces of ice, each piece has exactly one digit between 0 and 9. He wants to construct his favourite number t. He realized that digits 6 and 9 are very similar, so he can rotate piece of ice with 6 to use as 9 (and vice versa). Similary, 2 and 5 work the same. There is no other pair of digits with similar effect. He called this effect "Digital Mimicry".

Sheldon favourite number is t. He wants to have as many instances of t as possible. How many instances he can construct using the given sequence of ice pieces. He can use any piece at most once. 


-----Input-----

The first line contains integer t (1 ≤ t ≤ 10000). The second line contains the sequence of digits on the pieces. The length of line is equal to the number of pieces and between 1 and 200, inclusive. It contains digits between 0 and 9.


-----Output-----

Print the required number of instances.


-----Examples-----
Input
42
23454

Output
2

Input
169
12118999

Output
1



-----Note-----

This problem contains very weak pretests.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The numbers of all offices in the new building of the Tax Office of IT City will have lucky numbers.

Lucky number is a number that consists of digits 7 and 8 only. Find the maximum number of offices in the new building of the Tax Office given that a door-plate can hold a number not longer than *n* digits.

Input Specification:
The only line of input contains one integer *n* (1<=≤<=*n*<=≤<=55) — the maximum length of a number that a door-plate can hold.

Output Specification:
Output one integer — the maximum number of offices, than can have unique lucky numbers not longer than *n* digits.

Demo Input:
['2\n']

Demo Output:
['6']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A plane is flying at a constant height of $h$ meters above the ground surface. Let's consider that it is flying from the point $(-10^9, h)$ to the point $(10^9, h)$ parallel with $Ox$ axis.

A glider is inside the plane, ready to start his flight at any moment (for the sake of simplicity let's consider that he may start only when the plane's coordinates are integers). After jumping from the plane, he will fly in the same direction as the plane, parallel to $Ox$ axis, covering a unit of distance every second. Naturally, he will also descend; thus his second coordinate will decrease by one unit every second.

There are ascending air flows on certain segments, each such segment is characterized by two numbers $x_1$ and $x_2$ ($x_1 < x_2$) representing its endpoints. No two segments share any common points. When the glider is inside one of such segments, he doesn't descend, so his second coordinate stays the same each second. The glider still flies along $Ox$ axis, covering one unit of distance every second.  [Image] If the glider jumps out at $1$, he will stop at $10$. Otherwise, if he jumps out at $2$, he will stop at $12$. 

Determine the maximum distance along $Ox$ axis from the point where the glider's flight starts to the point where his flight ends if the glider can choose any integer coordinate to jump from the plane and start his flight. After touching the ground the glider stops altogether, so he cannot glide through an ascending airflow segment if his second coordinate is $0$.


-----Input-----

The first line contains two integers $n$ and $h$ $(1 \le n \le 2\cdot10^{5}, 1 \le h \le 10^{9})$ — the number of ascending air flow segments and the altitude at which the plane is flying, respectively.

Each of the next $n$ lines contains two integers $x_{i1}$ and $x_{i2}$ $(1 \le x_{i1} < x_{i2} \le 10^{9})$ — the endpoints of the $i$-th ascending air flow segment. No two segments intersect, and they are given in ascending order.


-----Output-----

Print one integer — the maximum distance along $Ox$ axis that the glider can fly from the point where he jumps off the plane to the point where he lands if he can start his flight at any integer coordinate.


-----Examples-----
Input
3 4
2 5
7 9
10 11

Output
10

Input
5 10
5 7
11 12
16 20
25 26
30 33

Output
18

Input
1 1000000000
1 1000000000

Output
1999999999



-----Note-----

In the first example if the glider can jump out at $(2, 4)$, then the landing point is $(12, 0)$, so the distance is $12-2 = 10$.

In the second example the glider can fly from $(16,10)$ to $(34,0)$, and the distance is $34-16=18$.

In the third example the glider can fly from $(-100,1000000000)$ to $(1999999899,0)$, so the distance is $1999999899-(-100)=1999999999$.

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