vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Despite his bad reputation, Captain Flint is a friendly person (at least, friendly to animals). Now Captain Flint is searching worthy sailors to join his new crew (solely for peaceful purposes). A sailor is considered as worthy if he can solve Flint's task.

Recently, out of blue Captain Flint has been interested in math and even defined a new class of integers. Let's define a positive integer x as nearly prime if it can be represented as p ⋅ q, where 1 < p < q and p and q are prime numbers. For example, integers 6 and 10 are nearly primes (since 2 ⋅ 3 = 6 and 2 ⋅ 5 = 10), but integers 1, 3, 4, 16, 17 or 44 are not.

Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.

Uncle Bogdan easily solved the task and joined the crew. Can you do the same?

Input

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

Next t lines contain test cases — one per line. The first and only line of each test case contains the single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number Flint guessed.

Output

For each test case print: 

  * YES and 4 different positive integers such that at least 3 of them are nearly prime and their sum is equal to n (if there are multiple answers print any of them); 
  * NO if there is no way to represent n as the sum of 4 different positive integers where at least 3 of them are nearly prime. 

You can print each character of YES or NO in any case.

Example

Input


7
7
23
31
36
44
100
258


Output


NO
NO
YES
14 10 6 1
YES
5 6 10 15
YES
6 7 10 21
YES
2 10 33 55
YES
10 21 221 6

Note

In the first and second test cases, it can be proven that there are no four different positive integers such that at least three of them are nearly prime.

In the third test case, n=31=2 ⋅ 7 + 2 ⋅ 5 + 2 ⋅ 3 + 1: integers 14, 10, 6 are nearly prime.

In the fourth test case, n=36=5 + 2 ⋅ 3 + 2 ⋅ 5 + 3 ⋅ 5: integers 6, 10, 15 are nearly prime.

In the fifth test case, n=44=2 ⋅ 3 + 7 + 2 ⋅ 5 + 3 ⋅ 7: integers 6, 10, 21 are nearly prime.

In the sixth test case, n=100=2 + 2 ⋅ 5 + 3 ⋅ 11 + 5 ⋅ 11: integers 10, 33, 55 are nearly prime.

In the seventh test case, n=258=2 ⋅ 5 + 3 ⋅ 7 + 13 ⋅ 17 + 2 ⋅ 3: integers 10, 21, 221, 6 are nearly prime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the number of bracket sequences.

Each of the following $n$ lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".

The sum of lengths of all bracket sequences in the input is at most $5 \cdot 10^5$.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.


-----Output-----

Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.


-----Examples-----
Input
7
)())
)
((
((
(
)
)

Output
2

Input
4
(
((
(((
(())

Output
0

Input
2
(())
()

Output
1



-----Note-----

In the first example, it's optimal to construct two pairs: "((     )())" and "(     )".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are lots of contest coming up on HackerEarth and it is in urgent need of lots of problems. So it calls a meeting of all the problem setters in the team.

There are N problem setters in HackerEarth. Everybody has a fixed price for preparing a problem. This is given by the array prices[ ] and all elements of the array are distinct. Obviously the higher charged setters are more experienced and can easily do the task assigned to its lower charged setters.

The contest moderator AltF4, assigns a certain number of tasks to each of the setter. This is given by the array tasks[ ]. The finance team calculates the total cost to the company as sum of price[i] * tasks[i] for all i. 

This was simple. But the setters have now grown greedy. They need extra incentives to meet their busy schedule, transportation and accommodation costs. So everybody decides that if HackerEarth needs them and invites them to create problems, they would charge for extra K tasks to meet these surcharges. 

For example if N = 2, prices of the setters are {10, 50} and AltF4 needs tasks from both as {10, 20} the cost to company would have been 10 x 10 + 50 x 20 = 1100. With the new law of surcharges with K = 10, there are 2 possibilities. 
1st setter does 10 tasks and 2nd setter does 20 tasks. Cost is 10 x 20 + 50 x 30 = 1700.
2nd setter does all 30 tasks.  Cost is 50 x 40 = 2000.

In this case it is better to invite both the setters and do their tasks. Note that 1st setter cannot do the tasks of the 2nd setter because he is not that much experienced (lesser price).
However, if K would have been 50, then analyzing the two possiblities:
1st setter does 10 tasks and 2nd setter does 20 tasks. Cost is 10 x 60 + 50 x 70 = 4100.
2nd setter does all 30 tasks. Cost is 50 x 80 = 4000.

In this case it is better to invite only the 2nd setter and let him do the tasks of the 1st setter as well.
Given the N, K, and the arrays prices[ ] and tasks[ ], your job is the help the finance team calculate the minimum cost possible for the company for doing all tasks.

Input & Output:
The first line contains the number of test cases T. The first line of every test case contains two integers N K separated by space. The next two lines contains the arrays prices and tasks respectively. All numbers are space separated. 

For each test case, output the minimum possible cost to the company and help the finance team.

Constraints:
T ≤ 25
1 ≤ N, prices[i], tasks[i] ≤ 2000
0 ≤ K ≤ 2000
 

SAMPLE INPUT
2
2 10
10 50
10 20
2 50
10 50
10 20

SAMPLE OUTPUT
1700
4000

Explanation

Provided in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer n. Output its binary notation.

Input

The only line of input data contains an integer n (1 ≤ n ≤ 106).

Output

Output the binary notation of n (without any leading zeros).

Examples

Input

5


Output

101


Input

101


Output

1100101

Note

In the first example 5 = 1 * 22 + 0 * 21 + 1 * 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two words rhyme if their last 3 letters are a match. Given N words, print the test case number (of the format Case : num) followed by the rhyming words in separate line adjacent to each other.

The output can be in anyorder.

-----Input-----
First line contains the number of test case T

The next line contains the number of words N

Next N words follow . They’ll contain only alphabets from ‘a’-‘z’.

-----Output-----
Print case number (for each test case) of the format Case : num followed by the words that rhyme in a new line.

-----Constraints-----
1 <= T <= 5

1 <= N <= 1000

3 <= length of each word <= 1000

-----Example-----
Input:
3
3
nope qwerty hope
5 
brain drain request grain nest
4
these words dont rhyme


Output:
Case : 1
hope nope
qwerty
Case : 2
brain drain grain
nest request
Case : 3
these
dont
words
rhyme



-----Explanation-----
Case : 2

brain drain grain

nest request

Case : 3

these

dont

words

rhyme
Explanation for case 1: since hope and nope rhyme (suffix “ope” matches), we print them in the same line and qwerty In a new line.

Note that

qwerty

nope hope

is also correct (the output can be in any order )

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
3R2 - Standby for Action

Our dear Cafe's owner, JOE Miller, will soon take part in a new game TV-show "1 vs. $n$"!

The game goes in rounds, where in each round the host asks JOE and his opponents a common question. All participants failing to answer are eliminated. The show ends when only JOE remains (we assume that JOE never answers a question wrong!).

For each question JOE answers, if there are $s$ ($s > 0$) opponents remaining and $t$ ($0 \le t \le s$) of them make a mistake on it, JOE receives $\displaystyle\frac{t}{s}$ dollars, and consequently there will be $s - t$ opponents left for the next question.

JOE wonders what is the maximum possible reward he can receive in the best possible scenario. Yet he has little time before show starts, so can you help him answering it instead?


-----Input-----

The first and single line contains a single integer $n$ ($1 \le n \le 10^5$), denoting the number of JOE's opponents in the show.


-----Output-----

Print a number denoting the maximum prize (in dollars) JOE could have.

Your answer will be considered correct if it's absolute or relative error won't exceed $10^{-4}$. In other words, if your answer is $a$ and the jury answer is $b$, then it must hold that $\frac{|a - b|}{max(1, b)} \le 10^{-4}$.


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

Output
1.000000000000

Input
2

Output
1.500000000000



-----Note-----

In the second example, the best scenario would be: one contestant fails at the first question, the other fails at the next one. The total reward will be $\displaystyle \frac{1}{2} + \frac{1}{1} = 1.5$ dollars.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a new prodigy in town and he has challenged people to a game. They have to give him an integer N and he will immediately respond with a number which has more than N factors.
What the prodigy really does is to do some complex calculations in his head to find out the smallest integer with more than N factors. However, he has a weakness - he knows to do those calculation only on numbers up to 1019, so if the answer to be reported is more than 1019, he will not be able to come up with his solution and will lose the game.
Given the integer the people give to the prodigy, you need to report whether he wins the game or not. If he wins, also output his answer.

-----Input-----
The first line of input contains T (T ≤ 25), the number of test cases. Following this are T lines, each containing an integer N (1 ≤ N ≤ 109) - the number which is given to the prodigy.

-----Output-----
Output one line per test case. If the smallest integer X with more than N factors is bigger than 1019 so that the prodigy does not win, print "lose". Otherwise print "win X" (quotes for clarity).

-----Example-----
Input:
3
3
5
12345678

Output:
win 6
win 12
lose

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year and North Pole

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere. The length of the equator and any meridian is considered to be exactly 40<=000 kilometers. Thus, travelling from North Pole to South Pole or vice versa takes exactly 20<=000 kilometers.

Limak, a polar bear, lives on the North Pole. Close to the New Year, he helps somebody with delivering packages all around the world. Instead of coordinates of places to visit, Limak got a description how he should move, assuming that he starts from the North Pole. The description consists of *n* parts. In the *i*-th part of his journey, Limak should move *t**i* kilometers in the direction represented by a string *dir**i* that is one of: "North", "South", "West", "East".

Limak isn’t sure whether the description is valid. You must help him to check the following conditions:
 -  If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South. -  If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North. -  The journey must end on the North Pole. 
Check if the above conditions are satisfied and print "YES" or "NO" on a single line.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=50).

The *i*-th of next *n* lines contains an integer *t**i* and a string *dir**i* (1<=≤<=*t**i*<=≤<=106, ) — the length and the direction of the *i*-th part of the journey, according to the description Limak got.

Output Specification:
Print "YES" if the description satisfies the three conditions, otherwise print "NO", both without the quotes.

Demo Input:
['5\n7500 South\n10000 East\n3500 North\n4444 West\n4000 North\n', '2\n15000 South\n4000 East\n', '5\n20000 South\n1000 North\n1000000 West\n9000 North\n10000 North\n', '3\n20000 South\n10 East\n20000 North\n', '2\n1000 North\n1000 South\n', '4\n50 South\n50 North\n15000 South\n15000 North\n']

Demo Output:
['YES\n', 'NO\n', 'YES\n', 'NO\n', 'NO\n', 'YES\n']

Note:
Drawings below show how Limak's journey would look like in first two samples. In the second sample the answer is "NO" because he doesn't end on the North Pole.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you heard about Megamind? Megamind and Metro Man are two aliens who came to earth. Megamind wanted to destroy the earth, while Metro Man wanted to stop him and protect mankind. After a lot of fighting, Megamind finally threw Metro Man up into the sky. Metro Man was defeated and was never seen again. Megamind wanted to be a super villain. He believed that the difference between a villain and a super villain is nothing but presentation. Megamind became bored, as he had nobody or nothing to fight against since Metro Man was gone. So, he wanted to create another hero against whom he would fight for recreation. But accidentally, another villain named Hal Stewart was created in the process, who also wanted to destroy the earth. Also, at some point Megamind had fallen in love with a pretty girl named Roxanne Ritchi. This changed him into a new man. Now he wants to stop Hal Stewart for the sake of his love. So, the ultimate fight starts now.

* Megamind has unlimited supply of guns named Magic-48. Each of these guns has `shots` rounds of magic spells.
* Megamind has perfect aim. If he shoots a magic spell it will definitely hit Hal Stewart. Once hit, it decreases the energy level of Hal Stewart by `dps` units.
* However, since there are exactly `shots` rounds of magic spells in each of these guns, he may need to swap an old gun with a fully loaded one. This takes some time. Let’s call it swapping period. 
* Since Hal Stewart is a mutant, he has regeneration power. His energy level increases by `regen` unit during a swapping period. 
* Hal Stewart will be defeated immediately once his energy level becomes zero or negative. 
* Hal Stewart initially has the energy level of `hp` and Megamind has a fully loaded gun in his hand.
* Given the values of `hp`, `dps`, `shots` and `regen`, find the minimum number of times Megamind needs to shoot to defeat Hal Stewart. If it is not possible to defeat him,  return `-1` instead.

# Example
Suppose, `hp` = 13, `dps` = 4, `shots` = 3 and `regen` = 1. There are 3 rounds of spells in the gun. Megamind shoots all of them. Hal Stewart’s energy level decreases by 12 units, and thus his energy level becomes 1. Since Megamind’s gun is now empty, he will get a new gun and thus it’s a swapping period. At this time, Hal Stewart’s energy level will increase by 1 unit and will become 2. However, when Megamind shoots the next spell, Hal’s energy level will drop by 4 units and will become −2, thus defeating him. So it takes 4 shoots in total to defeat Hal Stewart. However, in this same example if Hal’s regeneration power was 50 instead of 1, it would have been impossible to defeat Hal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Volodya has recently visited a very odd town. There are N tourist attractions in the town and every two of them are connected by a bidirectional road. Each road has some travel price (natural number) assigned to it and all prices are distinct. But the most striking thing about this town is that each city sightseeing tour has the same total price! That is, if we choose any city sightseeing tour — a cycle which visits every attraction exactly once — the sum of the costs of the tour roads is independent of the tour. Volodya is curious if you can find such price system with all road prices not greater than 1000.

Input

Input contains just one natural number (3 ≤ N ≤ 20) — the number of town attractions.

Output

Output should contain N rows containing N positive integer numbers each — the adjacency matrix of the prices graph (thus, j-th number in i-th row should be equal to the price of the road between the j-th and the i-th attraction). Diagonal numbers should be equal to zero. All numbers should not be greater than 1000. All prices should be positive and pairwise distinct. If there are several solutions, output any of them.

Examples

Input

3


Output

0 3 4 
3 0 5 
4 5 0 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Students went into a class to write a test and sat in some way. The teacher thought: "Probably they sat in this order to copy works of each other. I need to rearrange them in such a way that students that were neighbors are not neighbors in a new seating."

The class can be represented as a matrix with *n* rows and *m* columns with a student in each cell. Two students are neighbors if cells in which they sit have a common side.

Let's enumerate students from 1 to *n*·*m* in order of rows. So a student who initially sits in the cell in row *i* and column *j* has a number (*i*<=-<=1)·*m*<=+<=*j*. You have to find a matrix with *n* rows and *m* columns in which all numbers from 1 to *n*·*m* appear exactly once and adjacent numbers in the original matrix are not adjacent in it, or determine that there is no such matrix.

Input Specification:
The only line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105; *n*·*m*<=≤<=105) — the number of rows and the number of columns in the required matrix.

Output Specification:
If there is no such matrix, output "NO" (without quotes). 

Otherwise in the first line output "YES" (without quotes), and in the next *n* lines output *m* integers which form the required matrix.

Demo Input:
['2 4\n', '2 1\n']

Demo Output:
['YES\n5 4 7 2 \n3 6 1 8 \n', 'NO\n']

Note:
In the first test case the matrix initially looks like this:

It's easy to see that there are no two students that are adjacent in both matrices.

In the second test case there are only two possible seatings and in both of them students with numbers 1 and 2 are neighbors.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {a1, a2, ..., an}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i - 1)-th envelope respectively. Chain size is the number of envelopes in the chain. 

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes. 

Peter has very many envelopes and very little time, this hard task is entrusted to you.

Input

The first line contains integers n, w, h (1 ≤ n ≤ 5000, 1 ≤ w, h ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers wi and hi — width and height of the i-th envelope (1 ≤ wi, hi ≤ 106).

Output

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

Examples

Input

2 1 1
2 2
2 2


Output

1
1 


Input

3 3 3
5 4
12 11
9 8


Output

3
1 3 2

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