vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have a set of birthday cake candles. Each of such candles represents a digit between 0 and 9, inclusive.

<image> Example of birthday cake candles.

Let's denote the candle representing the digit d as d-candle.

Your set contains c_0 instances of 0-candles, c_1 instances of 1-candles and so on. So, the total number of candles is c_0+c_1+...+c_9.

These digits are needed to wish your cat a happy birthday. For each birthday, starting with the first, you want to compose the age of the cat using the digits from the set.

Since you light candles for a very short time, candles don't have time to burn out. For this reason you can reuse candles an arbitrary number of times (therefore your set of candles never changes).

For example, if you have one instance of each digit (i.e. c_0=c_1=...=c_9=1), you can compose any number from 1 to 10 using this set, but you cannot compose 11.

You have to determine the first birthday, on which you cannot compose the age of the cat using the candles from your set. In other words, find the minimum number y such that all numbers from 1 to y-1 can be composed by digits from your set, but y cannot be composed.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input.

The only line of each test case contains ten integer numbers c_0, c_1, ..., c_9 (0 ≤ c_i ≤ 10^5) — the number of 0-candles, 1-candles, 2-candles and so on.

It is guaranteed that the sum of all c_i in the input does not exceed 10^6.

Output

For each test case, output one integer in single line — the minimum age which cannot be composed by candles from your set. Please note that the age can be quite large (it may exceed the standard 64-bit integer types in your programming language).

Example

Input


4
1 1 1 1 1 1 1 1 1 1
0 0 1 1 2 2 3 3 4 4
1 2 1 2 1 3 1 0 0 0
0 1 2 1 4 3 1 1 2 1


Output


11
1
7
10

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Everyone knows that hobbits love to organize all sorts of parties and celebrations. There are *n* hobbits living in the Shire. They decided to organize the Greatest Party (GP) that would last for several days. Next day the hobbits wrote a guest list, some non-empty set containing all the inhabitants of the Shire. To ensure that everybody enjoy themselves and nobody gets bored, for any two days (say, days A and B) of the GP there existed at least one hobbit, invited to come on day A and on day B. However, to ensure that nobody has a row, for any three different days A, B, C there shouldn't be a hobbit invited on days A, B and C. The Shire inhabitants are keen on keeping the GP going for as long as possible. Your task is given number *n*, to indicate the GP's maximum duration and the guest lists for each day.

Input Specification:
The first line contains an integer *n* (3<=≤<=*n*<=≤<=10000), representing the number of hobbits.

Output Specification:
In the first output line print a number *k* — the maximum duration of GP in days. Then on *k* lines print the guest lists, (the guests should be separated by spaces). Print each guest list on the single line. Each list can contain an arbitrary positive number of hobbits. The hobbits are numbered with integers from 1 to *n*.

Demo Input:
['4\n', '5\n']

Demo Output:
['3\n1 2 \n1 3 \n2 3 \n', '3\n1 2 \n1 3 \n2 3 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the school computer room there are n servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are m_{i} tasks assigned to the i-th server.

In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression m_{a} - m_{b}, where a is the most loaded server and b is the least loaded one.

In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.

Write a program to find the minimum number of seconds needed to balance the load of servers.


-----Input-----

The first line contains positive number n (1 ≤ n ≤ 10^5) — the number of the servers. 

The second line contains the sequence of non-negative integers m_1, m_2, ..., m_{n} (0 ≤ m_{i} ≤ 2·10^4), where m_{i} is the number of tasks assigned to the i-th server.


-----Output-----

Print the minimum number of seconds required to balance the load.


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

Output
2

Input
7
10 11 10 11 10 11 11

Output
0

Input
5
1 2 3 4 5

Output
3



-----Note-----

In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.

In the second example the load is already balanced.

A possible sequence of task movements for the third example is:  move a task from server #4 to server #1 (the sequence m becomes: 2 2 3 3 5);  then move task from server #5 to server #1 (the sequence m becomes: 3 2 3 3 4);  then move task from server #5 to server #2 (the sequence m becomes: 3 3 3 3 3). 

The above sequence is one of several possible ways to balance the load of servers in three seconds.

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

Digital Cypher assigns a unique number to each letter of the alphabet:

```
 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
```

In the encrypted word we write the corresponding numbers instead of the letters. For example, the word `scout` becomes:

```
 s  c  o  u  t
19  3 15 21 20
```
Then we add to each number a digit from the key (repeated if necessary). For example if the key is `1939`:

```
   s  c  o  u  t
  19  3 15 21 20
 + 1  9  3  9  1
 ---------------
  20 12 18 30 21
  
   m  a  s  t  e  r  p  i  e  c  e
  13  1 19 20  5 18 16  9  5  3  5
+  1  9  3  9  1  9  3  9  1  9  3
  --------------------------------
  14 10 22 29  6 27 19 18  6  12 8
```

# Task

Write a function that accepts a `message` string  and an array of integers `code`. As the result, return the `key` that was used to encrypt the `message`. The `key` has to be shortest of all possible keys that can be used to code the `message`: i.e. when the possible keys are `12` , `1212`, `121212`, your solution should return `12`.

#### Input / Output:

* The `message` is a string containing only lowercase letters.
* The `code` is an array of positive integers.
* The `key` output is a positive integer.

# Examples

```python
find_the_key("scout", [20, 12, 18, 30, 21]) # -->  1939
find_the_key("masterpiece", [14, 10, 22, 29, 6, 27, 19, 18, 6, 12, 8]) # -->  1939
find_the_key("nomoretears", [15, 17, 14, 17, 19, 7, 21, 7, 2, 20, 20]) # -->  12
```

# Digital cypher series
- [Digital cypher vol 1](https://www.codewars.com/kata/592e830e043b99888600002d)
- [Digital cypher vol 2](https://www.codewars.com/kata/592edfda5be407b9640000b2)
- [Digital cypher vol 3 - missing key](https://www.codewars.com/kata/5930d8a4b8c2d9e11500002a)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's say string s has period k if s_i = s_{i + k} for all i from 1 to |s| - k (|s| means length of string s) and k is the minimum positive integer with this property.

Some examples of a period: for s="0101" the period is k=2, for s="0000" the period is k=1, for s="010" the period is k=2, for s="0011" the period is k=4.

You are given string t consisting only of 0's and 1's and you need to find such string s that:

  1. String s consists only of 0's and 1's; 
  2. The length of s doesn't exceed 2 ⋅ |t|; 
  3. String t is a subsequence of string s; 
  4. String s has smallest possible period among all strings that meet conditions 1—3. 



Let us recall that t is a subsequence of s if t can be derived from s by deleting zero or more elements (any) without changing the order of the remaining elements. For example, t="011" is a subsequence of s="10101".

Input

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

Next T lines contain test cases — one per line. Each line contains string t (1 ≤ |t| ≤ 100) consisting only of 0's and 1's.

Output

Print one string for each test case — string s you needed to find. If there are multiple solutions print any one of them.

Example

Input


4
00
01
111
110


Output


00
01
11111
1010

Note

In the first and second test cases, s = t since it's already one of the optimal solutions. Answers have periods equal to 1 and 2, respectively.

In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string s. String s has period equal to 1.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
On a history lesson the teacher asked Vasya to name the dates when *n* famous events took place. He doesn't remembers the exact dates but he remembers a segment of days [*l**i*,<=*r**i*] (inclusive) on which the event could have taken place. However Vasya also remembers that there was at most one event in one day. Help him choose such *n* dates of famous events that will fulfill both conditions. It is guaranteed that it is possible.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=100) — the number of known events. Then follow *n* lines containing two integers *l**i* and *r**i* each (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=107) — the earliest acceptable date and the latest acceptable date of the *i*-th event.

Output Specification:
Print *n* numbers — the dates on which the events took place. If there are several solutions, print any of them. It is guaranteed that a solution exists.

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

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

Note:
none

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

David is playing a video game set in a dungeon. The dungeon has n interesting points and m one way tunnels connecting those points. The i-th tunnel starts at point ai and ends at point bi and takes ci units of time to traverse. Note that it may be possible that there are two tunnels connecting the same pair of points, and even more strangely, a tunnel that goes back to the same point.

David is currently at the point labeled 0, and wishes to travel to the point n-1 using the smallest amount of time.

David discovered that some points become dangerous at some moments of time. More specifically, for each point, David found an integer oi such that point i is dangerous at all times t satisfying t = oi modulo p. The integer p is the same for every single intersection.

David needs to always be in constant motion, and can't wait at a point. Additionally, he will always be safe in a tunnel, but cannot arrive at a point at the moment it becomes dangerous. 

Help David determine the fastest time he can reach his destination.

Input Format:

The first line of input will contain three space separated integers n,m,p.
The next line of input will contain n space separted integers oi.
The next m lines of input will each contain 3 integers ai, bi, ci

Output Format:

If it is impossible for David to reach point n-1, print -1. Otherwise, print the smallest amount of time it will take David to reach n-1.

Constraints:

For all subtasks:
0 ≤ ai, bi ≤ n-1 
0 ≤ ci ≤ 10^9
0 ≤ oi ≤ p-1

25 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 250
2 ≤ p ≤ 50

30 pts:
2 ≤ n ≤ 100
1 ≤ m ≤ 10000
2 ≤ p ≤ 500

30 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 2500
2 ≤ p ≤ 10^9

15 pts:
2 ≤ n ≤ 1000
1 ≤ m ≤ 10000
2 ≤ p ≤ 10^9

SAMPLE INPUT
4 5 5
1 0 2 3
0 1 8
0 2 2
1 3 5
2 3 3
1 2 6

SAMPLE OUTPUT
17

Explanation

The shortest path here is 0->1->2->3.
We can't take the tunnel 0->2 immediately, since point 2 will be dangerous at time T=2.
We can't take the tunnel 1->3 after 0->1, since point 3 will be dangerous at time T=13.
Instead, this roundabout path is the only way for David to get to the exit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
```
*************************
*  Create a frame!      *
*           __     __   *
*          /  \~~~/  \  *
*    ,----(     ..    ) *
*   /      \__     __/  *
*  /|         (\  |(    *
* ^  \  /___\  /\ |     *
*    |__|   |__|-..     *
*************************
```

Given an array of strings and a character to be used as border, output the frame with the content inside.

Notes:

* Always keep a space between the input string and the left and right borders.
* The biggest string inside the array should always fit in the frame.
* The input array is never empty.


## Example

`frame(['Create', 'a', 'frame'], '+')`

Output:
```
++++++++++
+ Create +
+ a      +
+ frame  +
++++++++++
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $t$ consisting of $n$ lowercase Latin letters and an integer number $k$.

Let's define a substring of some string $s$ with indices from $l$ to $r$ as $s[l \dots r]$.

Your task is to construct such string $s$ of minimum possible length that there are exactly $k$ positions $i$ such that $s[i \dots i + n - 1] = t$. In other words, your task is to construct such string $s$ of minimum possible length that there are exactly $k$ substrings of $s$ equal to $t$.

It is guaranteed that the answer is always unique.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 50$) — the length of the string $t$ and the number of substrings.

The second line of the input contains the string $t$ consisting of exactly $n$ lowercase Latin letters.


-----Output-----

Print such string $s$ of minimum possible length that there are exactly $k$ substrings of $s$ equal to $t$.

It is guaranteed that the answer is always unique.


-----Examples-----
Input
3 4
aba

Output
ababababa

Input
3 2
cat

Output
catcat

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Pari and Arya are playing a game called Remainders.

Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value <image>. There are n ancient numbers c1, c2, ..., cn and Pari has to tell Arya <image> if Arya wants. Given k and the ancient values, tell us if Arya has a winning strategy independent of value of x or not. Formally, is it true that Arya can understand the value <image> for any positive integer x?

Note, that <image> means the remainder of x after dividing it by y.

Input

The first line of the input contains two integers n and k (1 ≤ n, k ≤ 1 000 000) — the number of ancient integers and value k that is chosen by Pari.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 1 000 000).

Output

Print "Yes" (without quotes) if Arya has a winning strategy independent of value of x, or "No" (without quotes) otherwise.

Examples

Input

4 5
2 3 5 12


Output

Yes


Input

2 7
2 3


Output

No

Note

In the first sample, Arya can understand <image> because 5 is one of the ancient numbers.

In the second sample, Arya can't be sure what <image> is. For example 1 and 7 have the same remainders after dividing by 2 and 3, but they differ in remainders after dividing by 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Given two integers `a` and `b`, return the sum of the numerator and the denominator of the reduced fraction `a/b`.

# Example

For `a = 2, b = 4`, the result should be `3`

Since `2/4 = 1/2 => 1 + 2 = 3`.

For `a = 10, b = 100`, the result should be `11`

Since `10/100 = 1/10 => 1 + 10 = 11`.

For `a = 5, b = 5`, the result should be `2`

Since `5/5 = 1/1 => 1 + 1 = 2`.

# Input/Output


- `[input]` integer `a`

The numerator, `1 ≤ a ≤ 2000`.


- `[input]` integer `b`

The denominator, `1 ≤ b ≤ 2000`.


- `[output]` an integer

The sum of the numerator and the denominator of the reduces fraction.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zombies have placed themselves at every junction in Bucharest. Each junction 'i' initially has a presence of ai number of zombies. Every timestep, each zombie randomly chooses one of its neighboring junctions and walks towards it. Each neighboring junction is choosen by the zombie with an equal probability. In order to safegaurd the citizens of Bucharest we need to find out the expected number of zombies at every junction after 'k' timesteps. 

The network of Bucharest is given as an edge list.  

Input Format  

t - the number of test cases. 't' cases follow.
n, m, k - 'n' junctions (nodes) in Bucharest, 'm' roads (edges) and 'k' time steps. 
This is followed by m lines containing 1 edge on each line. Each edge is denoted by 2 integers representing the nodes it connects, which can range from 0 to n-1.  All the edges are bidirectional. A node cannot connect itself. 
This is followed by n lines, where the i^{th} line contains the initial number of Zombies at the location ai.

Output Format 

Output the number of zombies (rounded of to its nearest integer) in the 5 most highly populated junctions after 'k' timesteps.

Constraints 

1<=t<=5

5<=n<=100000

1<=m<= 200000

1<=k<=10000000

1<=ai<=1000

Sample Input  

1

10 18 100

0 8 

0 5 

1 2 

1 5 

2 8 

2 4 

2 5 

2 6 

3 5 

4 8 

4 6 

4 7 

5 8 

5 9 

6 8 

6 9 

7 9 

8 9 

1

1

1

1

1

1

1

1

1

1

Sample Output 

2 2 1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list of size N, your task is to complete the function isLengthEvenOrOdd() which contains head of the linked list and check whether the length of linked list is even or odd.
Input:
The input line contains T, denoting the number of testcases. Each testcase contains two lines. the first line contains N(size of the linked list). the second line contains N elements of the linked list separated by space.
Output:
For each testcase in new line, print "even"(without quotes) if the length is even else "odd"(without quotes) if the length is odd.
User Task:
Since this is a functional problem you don't have to worry about input, you just have to  complete the function isLengthEvenOrOdd() which takes head of the linked list as input parameter and returns 0 if the length of the linked list is even otherwise returns 1.
Constraints:
1 <= T <= 100
1 <= N <= 10^{3}
1 <= A[i] <= 10^{3}
Example:
Input:
2
3
9 4 3
6
12 52 10 47 95 0
Output:
Odd
Even
Explanation:
Testcase 1: The length of linked list is 3 which is odd.
Testcase 2: The length of linked list is 6 which is even.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is at an all-you-can-eat restaurant.
The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i-th dish, whose deliciousness is B_i.
The restaurant has the following rules:
 - You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.
 - You cannot order the same kind of dish more than once.
 - Until you finish eating the dish already served, you cannot order a new dish.
 - After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.
Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.
What is the maximum possible happiness achieved by making optimal choices?

-----Constraints-----
 - 2 \leq N \leq 3000
 - 1 \leq T \leq 3000
 - 1 \leq A_i \leq 3000
 - 1 \leq B_i \leq 3000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N T
A_1 B_1
:
A_N B_N

-----Output-----
Print the maximum possible happiness Takahashi can achieve.

-----Sample Input-----
2 60
10 10
100 100

-----Sample Output-----
110

By ordering the first and second dishes in this order, Takahashi's happiness will be 110.
Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of N elements and a number K. Split the given array into K subarrays such that the maximum subarray sum achievable out of K subarrays formed is minimum possible. Find that possible subarray sum.
Example 1:
Input:
N = 4, K = 3
arr[] = {1, 2, 3, 4}
Output: 4
Explanation:
Optimal Split is {1, 2}, {3}, {4}.
Maximum sum of all subarrays is 4,
which is minimum possible for 3 splits. 
Example 2:
Input:
N = 3, K = 2
A[] = {1, 1, 2}
Output:
2
Explanation:
Splitting the array as {1,1} and {2} is optimal.
This results in a maximum sum subarray of 2.
 
Your Task:
The task is to complete the function splitArray() which returns the maximum sum subarray after splitting the array into K subarrays such that maximum sum subarray is minimum possible.
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ N
1 ≤ arr[i] ≤ 10^{4}
Expected Time Complexity: O(N*log(sum(arr))).
Expected Auxiliary Space: O(1).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In a new version of the famous Pinball game, one of the most important parts of the game field is a sequence of *n* bumpers. The bumpers are numbered with integers from 1 to *n* from left to right. There are two types of bumpers. They are denoted by the characters '&lt;' and '&gt;'. When the ball hits the bumper at position *i* it goes one position to the right (to the position *i*<=+<=1) if the type of this bumper is '&gt;', or one position to the left (to *i*<=-<=1) if the type of the bumper at position *i* is '&lt;'. If there is no such position, in other words if *i*<=-<=1<=&lt;<=1 or *i*<=+<=1<=&gt;<=*n*, the ball falls from the game field.

Depending on the ball's starting position, the ball may eventually fall from the game field or it may stay there forever. You are given a string representing the bumpers' types. Calculate the number of positions such that the ball will eventually fall from the game field if it starts at that position.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the length of the sequence of bumpers. The second line contains the string, which consists of the characters '&lt;' and '&gt;'. The character at the *i*-th position of this string corresponds to the type of the *i*-th bumper.

Output Specification:
Print one integer — the number of positions in the sequence such that the ball will eventually fall from the game field if it starts at that position.

Demo Input:
['4\n&lt;&lt;&gt;&lt;\n', '5\n&gt;&gt;&gt;&gt;&gt;\n', '4\n&gt;&gt;&lt;&lt;\n']

Demo Output:
['2', '5', '0']

Note:
In the first sample, the ball will fall from the field if starts at position 1 or position 2.

In the second sample, any starting position will result in the ball falling from the field.

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