vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Having stayed home alone, Petya decided to watch forbidden films on the Net in secret. "What ungentlemanly behavior!" — you can say that, of course, but don't be too harsh on the kid. In his country films about the Martians and other extraterrestrial civilizations are forbidden. It was very unfair to Petya as he adored adventure stories that featured lasers and robots. 

Today Petya is watching a shocking blockbuster about the Martians called "R2:D2". What can "R2:D2" possibly mean? It might be the Martian time represented in the Martian numeral system. Petya knows that time on Mars is counted just like on the Earth (that is, there are 24 hours and each hour has 60 minutes). The time is written as "a:b", where the string a stands for the number of hours (from 0 to 23 inclusive), and string b stands for the number of minutes (from 0 to 59 inclusive). The only thing Petya doesn't know is in what numeral system the Martian time is written.

Your task is to print the radixes of all numeral system which can contain the time "a:b".

Input

The first line contains a single string as "a:b" (without the quotes). There a is a non-empty string, consisting of numbers and uppercase Latin letters. String a shows the number of hours. String b is a non-empty string that consists of numbers and uppercase Latin letters. String b shows the number of minutes. The lengths of strings a and b are from 1 to 5 characters, inclusive. Please note that strings a and b can have leading zeroes that do not influence the result in any way (for example, string "008:1" in decimal notation denotes correctly written time).

We consider characters 0, 1, ..., 9 as denoting the corresponding digits of the number's representation in some numeral system, and characters A, B, ..., Z correspond to numbers 10, 11, ..., 35.

Output

Print the radixes of the numeral systems that can represent the time "a:b" in the increasing order. Separate the numbers with spaces or line breaks. If there is no numeral system that can represent time "a:b", print the single integer 0. If there are infinitely many numeral systems that can represent the time "a:b", print the single integer -1.

Note that on Mars any positional numeral systems with positive radix strictly larger than one are possible.

Examples

Input

11:20


Output

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Input

2A:13


Output

0


Input

000B:00001


Output

-1

Note

Let's consider the first sample. String "11:20" can be perceived, for example, as time 4:6, represented in the ternary numeral system or as time 17:32 in hexadecimal system. 

Let's consider the second sample test. String "2A:13" can't be perceived as correct time in any notation. For example, let's take the base-11 numeral notation. There the given string represents time 32:14 that isn't a correct time.

Let's consider the third sample. String "000B:00001" can be perceived as a correct time in the infinite number of numeral systems. If you need an example, you can take any numeral system with radix no less than 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This week Arkady wanted to cook some pancakes (to follow ancient traditions) and make a problem about that. But then he remembered that one can't make a problem about stacking pancakes without working at a specific IT company, so he decided to bake the Napoleon cake instead.

To bake a Napoleon cake, one has to bake n dry layers first, and then put them on each other in one stack, adding some cream. Arkady started with an empty plate, and performed the following steps n times: 

  * place a new cake layer on the top of the stack; 
  * after the i-th layer is placed, pour a_i units of cream on top of the stack. 



When x units of cream are poured on the top of the stack, top x layers of the cake get drenched in the cream. If there are less than x layers, all layers get drenched and the rest of the cream is wasted. If x = 0, no layer gets drenched.

<image> The picture represents the first test case of the example.

Help Arkady determine which layers of the cake eventually get drenched when the process is over, and which don't.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 20 000). Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of layers in the cake.

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ n) — the amount of cream poured on the cake after adding each layer.

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

Output

For each test case, print a single line with n integers. The i-th of the integers should be equal to 1 if the i-th layer from the bottom gets drenched, and 0 otherwise.

Example

Input


3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0


Output


1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 0 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This night wasn't easy on Vasya. His favorite team lost, and he didn't find himself victorious either — although he played perfectly, his teammates let him down every time. He had to win at least one more time, but the losestreak only grew longer and longer... It's no wonder he didn't get any sleep this night at all.

In the morning, Vasya was waiting the bus to the university on the bus stop. Vasya's thoughts were hazy and so he couldn't remember the right bus' number quite right and got onto the bus with the number $n$.

In the bus, Vasya thought that he could get the order of the digits in the number of the bus wrong. Futhermore, he could "see" some digits several times, but the digits he saw were definitely in the real number of the bus. For example, if Vasya saw the number 2028, it could mean that the real bus number could be 2028, 8022, 2820 or just 820. However, numbers 80, 22208, 52 definitely couldn't be the number of the bus. Also, real bus number couldn't start with the digit 0, this meaning that, for example, number 082 couldn't be the real bus number too.

Given $n$, determine the total number of possible bus number variants.

Input Specification:
The first line contains one integer $n$ ($1 \leq n \leq 10^{18}$) — the number of the bus that was seen by Vasya. It is guaranteed that this number does not start with $0$.

Output Specification:
Output a single integer — the amount of possible variants of the real bus number.

Demo Input:
['97\n', '2028\n']

Demo Output:
['2\n', '13\n']

Note:
In the first sample, only variants $97$ and $79$ are possible.

In the second sample, the variants (in the increasing order) are the following: $208$, $280$, $802$, $820$, $2028$, $2082$, $2208$, $2280$, $2802$, $2820$, $8022$, $8202$, $8220$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

There are $N$ workers; each worker is of one of the following three types:
A *translator* translates some text from Chef's language to another langague.
An *author* writes some text in Chef's language.
An *author-translator* can both write a text in Chef's language and translate it to another language.

Chef wants to have some text written and translated into some language (different from Chef's language). Chef can't do either of those tasks, but he can hire workers. For each $i$ ($1 ≤ i ≤ N$), if he hires the $i$-th worker, he must pay that worker $c_{i}$ coins.

Help Chef find the minimum total number of coins he needs to pay to have a text written and translated. It is guaranteed that it is possible to write and translate a text.

------  Input ------
The first line of the input contains a single integer $N$ denoting the number of workers.
The second line contins $N$ space-separated integers $c_{1}, c_{2}, ..., c_{N}$ denoting the numbers of coins Chef has to pay each hired worker.
The third line contains $N$ space-separated integers $t_{1}, t_{2}, ..., t_{N}$ denoting the types of workers. For each valid $i$, the $i$-th worker is a translator if $t_{i} = 1$, an author if $t_{i} = 2$ or an author-translator if $t_{i} = 3$.

------  Output ------
Print a single line containing one integer — the minimum number of coins Chef has to pay.

------  Constraints ------
$1 ≤ N ≤ 1,000$
$1 ≤ c_{i} ≤ 100,000$ for each valid $i$
$1 ≤ t_{i} ≤ 3$ for each valid $i$

------  Subtasks ------
Subtask #1 (15 points): all workers are author-translators

Subtask #2 (85 points): original constraints

----- Sample Input 1 ------ 
5
1 3 4 6 8
1 2 1 2 3
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Chef can hire 2 workers: worker 1, who is a translator, and worker 2, who is an author. In total, he pays them $1 + 3 = 4$ coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a sequence $A_1, A_2, \ldots, A_N$; each element of this sequence is either $0$ or $1$. Appy gave him a string $S$ with length $Q$ describing a sequence of queries. There are two types of queries:
- '!': right-shift the sequence $A$, i.e. replace $A$ by another sequence $B_1, B_2, \ldots, B_N$ satisfying $B_{i+1} = A_i$ for each valid $i$ and $B_1 = A_N$
- '?': find the length of the longest contiguous subsequence of $A$ with length $\le K$ such that each element of this subsequence is equal to $1$
Answer all queries of the second type.

-----Input-----
- The first line of the input contains three space-separated integers $N$, $Q$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains a string with length $Q$ describing queries. Each character of this string is either '?', denoting a query of the second type, or '!', denoting a query of the first type.

-----Output-----
For each query of the second type, print a single line containing one integer — the length of the longest required subsequence.

-----Constraints-----
- $1 \le K \le N \le 10^5$
- $1 \le Q \le 3 \cdot 10^5$
- $0 \le A_i \le 1$ for each valid $i$
- $S$ contains only characters '?' and '!'

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le N \le 10^3$
- $1 \le Q \le 3 \cdot 10^3$
Subtask #2 (70 points): original constraints 

-----Example Input-----
5 5 3
1 1 0 1 1
?!?!?    

-----Example Output-----
2
3
3

-----Explanation-----
- In the first query, there are two longest contiguous subsequences containing only $1$-s: $A_1, A_2$ and $A_4, A_5$. Each has length $2$.
- After the second query, the sequence $A$ is $[1, 1, 1, 0, 1]$.
- In the third query, the longest contiguous subsequence containing only $1$-s is $A_1, A_2, A_3$.
- After the fourth query, $A = [1, 1, 1, 1, 0]$.
- In the fifth query, the longest contiguous subsequence containing only $1$-s is $A_1, A_2, A_3, A_4$ with length $4$. However, we only want subsequences with lengths $\le K$. One of the longest such subsequences is $A_2, A_3, A_4$, with length $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Black-and-White Cube

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a cube of size *k*<=×<=*k*<=×<=*k*, which consists of unit cubes. Two unit cubes are considered neighbouring, if they have common face.

Your task is to paint each of *k*3 unit cubes one of two colours (black or white), so that the following conditions must be satisfied:
 -  each white cube has exactly 2 neighbouring cubes of white color; -  each black cube has exactly 2 neighbouring cubes of black color.

Input Specification:
The first line contains integer *k* (1<=≤<=*k*<=≤<=100), which is size of the cube.

Output Specification:
Print -1 if there is no solution. Otherwise, print the required painting of the cube consequently by layers. Print a *k*<=×<=*k* matrix in the first *k* lines, showing how the first layer of the cube should be painted. In the following *k* lines print a *k*<=×<=*k* matrix — the way the second layer should be painted. And so on to the last *k*-th layer. Note that orientation of the cube in the space does not matter.

Mark a white unit cube with symbol "w" and a black one with "b". Use the format of output data, given in the test samples. You may print extra empty lines, they will be ignored.

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

Demo Output:
['-1\n', 'bb\nww\n\nbb\nww\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easy version of the problem. In this version, all numbers in the given array are distinct and the constraints on n are less than in the hard version of the problem.

You are given an array a of n integers (there are no equals elements in the array). You can perform the following operations on array elements:

  1. choose any index i (1 ≤ i ≤ n) and move the element a[i] to the begin of the array; 
  2. choose any index i (1 ≤ i ≤ n) and move the element a[i] to the end of the array. 



For example, if n = 5, a = [4, 7, 2, 3, 9], then the following sequence of operations can be performed: 

  * after performing the operation of the first type to the second element, the array a will become [7, 4, 2, 3, 9]; 
  * after performing the operation of the second type to the second element, the array a will become [7, 2, 3, 9, 4]. 



You can perform operations of any type any number of times in any order.

Find the minimum total number of operations of the first and second type that will make the a array sorted in non-decreasing order. In other words, what is the minimum number of operations that must be performed so the array satisfies the inequalities a[1] ≤ a[2] ≤ … ≤ a[n].

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases in the test. Then t test cases follow.

Each test case starts with a line containing an integer n (1 ≤ n ≤ 3000) — length of the array a.

Then follow n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9) — an array that needs to be sorted by the given operations. All numbers in the given array are distinct.

The sum of n for all test cases in one test does not exceed 3000.

Output

For each test case output one integer — the minimum total number of operations of the first and second type, which will make the array sorted in non-decreasing order.

Example

Input


4
5
4 7 2 3 9
5
3 5 8 1 7
5
1 4 5 7 12
4
0 2 1 3


Output


2
2
0
2

Note

In the first test case, you first need to move 3, and then 2 to the beginning of the array. Therefore, the desired sequence of operations: [4, 7, 2, 3, 9] → [3, 4, 7, 2, 9] → [2, 3, 4, 7, 9].

In the second test case, you need to move the 1 to the beginning of the array, and the 8 — to the end. Therefore, the desired sequence of operations: [3, 5, 8, 1, 7] → [1, 3, 5, 8, 7] → [1, 3, 5, 7, 8].

In the third test case, the array is already sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers l and r.

Let's call an integer x modest, if l ≤ x ≤ r.

Find a string of length n, consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one.

If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.

Input

The first line contains one integer l (1 ≤ l ≤ 10^{800}).

The second line contains one integer r (l ≤ r ≤ 10^{800}).

The third line contains one integer n (1 ≤ n ≤ 2 000).

Output

In the first line, print the maximum possible number of modest substrings.

In the second line, print a string of length n having exactly that number of modest substrings.

If there are multiple such strings, print the lexicographically smallest of them.

Examples

Input


1
10
3


Output


3
101


Input


1
11
3


Output


5
111


Input


12345
12346
6


Output


1
012345

Note

In the first example, string «101» has modest substrings «1», «10», «1».

In the second example, string «111» has modest substrings «1» (3 times) and «11» (2 times).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones.

Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \ldots, a_j$ ($1\leq i\leq j\leq n$) a substring of string $a$. 

You can apply the following operations any number of times:  Choose some substring of string $a$ (for example, you can choose entire string) and reverse it, paying $x$ coins for it (for example, «0101101» $\to$ «0111001»);  Choose some substring of string $a$ (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying $y$ coins for it (for example, «0101101» $\to$ «0110001»). 

You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring.

What is the minimum number of coins you need to spend to get a string consisting only of ones?


-----Input-----

The first line of input contains integers $n$, $x$ and $y$ ($1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring).

The second line contains the string $a$ of length $n$, consisting of zeros and ones.


-----Output-----

Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print $0$, if you do not need to perform any operations.


-----Examples-----
Input
5 1 10
01000

Output
11

Input
5 10 1
01000

Output
2

Input
7 2 3
1111111

Output
0



-----Note-----

In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «10000» $\to$ «11111».

The total cost of operations is $1 + 10 = 11$.

In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «11000» $\to$ «11111».

The overall cost is $1 + 1 = 2$.

In the third example, string already consists only of ones, so the answer is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two sisters Alice and Betty. You have $n$ candies. You want to distribute these $n$ candies between two sisters in such a way that:  Alice will get $a$ ($a > 0$) candies;  Betty will get $b$ ($b > 0$) candies;  each sister will get some integer number of candies;  Alice will get a greater amount of candies than Betty (i.e. $a > b$);  all the candies will be given to one of two sisters (i.e. $a+b=n$). 

Your task is to calculate the number of ways to distribute exactly $n$ candies between sisters in a way described above. Candies are indistinguishable.

Formally, find the number of ways to represent $n$ as the sum of $n=a+b$, where $a$ and $b$ are positive integers and $a>b$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of a test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^9$) — the number of candies you have.


-----Output-----

For each test case, print the answer — the number of ways to distribute exactly $n$ candies between two sisters in a way described in the problem statement. If there is no way to satisfy all the conditions, print $0$.


-----Example-----
Input
6
7
1
2
3
2000000000
763243547

Output
3
0
0
1
999999999
381621773



-----Note-----

For the test case of the example, the $3$ possible ways to distribute candies are:  $a=6$, $b=1$;  $a=5$, $b=2$;  $a=4$, $b=3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n elements, you must make it a co-prime array in as few moves as possible.

In each move you can insert any positive integral number you want not greater than 109 in any place in the array.

An array is co-prime if any two adjacent numbers of it are co-prime.

In the number theory, two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of elements in the given array.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

Output

Print integer k on the first line — the least number of elements needed to add to the array a to make it co-prime.

The second line should contain n + k integers aj — the elements of the array a after adding k elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array a by adding k elements to it.

If there are multiple answers you can print any one of them.

Example

Input

3
2 7 28


Output

1
2 7 9 28

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once, two trees forgot their place and started to grow into each other. One of the trees grew from the left, and the other from the right. On $n$ points, they collided.

Numbering the points $1, 2, \dots , n$ from left to right, the left tree ended up connecting all of them in a single subtree rooted in node $1$, such that every node’s children had larger numbers than the node itself. We can describe this subtree with a list of $n-1$ edges.

Similarly, the right tree also connected all nodes in a single subtree rooted in node $n$, with every node’s children having smaller numbers than the node itself. This yields an additional $n-1$ edges.

Now, given the full list of $2(n-1)$ edges, it is not necessarily easy to tell which edge belongs to which tree. Can you figure out a possible assignment, or determine that it is impossible for this collection to have been the union of two trees?

-----Input-----
The first line of input contains the integer $n$ ($2 \le n \le 10^5$). The next $2(n-1)$ lines each contain two integers $u, v$ ($1 \le u < v \le n$) indicating an edge joining the two nodes $u$ and $v$. A pair $(u, v)$ may be connected by more than one edge.

-----Output-----
If it is possible for the edges to be the union of two trees that grow left-to-right and right-to-left, output a string of length $2(n-1)$, where the $i$’s character is L if the $i$’th edge should come from the left tree, or R if it should come from the right tree. Otherwise, output the word “impossible” on a single line. If there are multiple solutions, you may output any one of them.

-----Explanation of Sample Inputs-----
In the first example, there are two solutions: LLRRRRLL and LLRLRRLR.

In the second example, there are no solutions. Note that LRLR is not valid, because it would involve the right tree growing backward, from left to right.

-----Examples-----
Sample Input:
5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3
Sample Output:
LLRRRRLL

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahesh Chaudhary likes playing with xor.
now he has n numbers and he wants to find out xor of all possible subsets and 
check out how many of them are distinct prime numbers i.e if two subsets have 
value 2 we need to count 2 only once

Input
first line contains t denoting number of test cases
next line contains n
and next line contains n numbers whose subset xor is to be found

output
print a number denoting prime numbers

Constraints
1 ≤ t<10  
1 ≤ n ≤ 1000    

SAMPLE INPUT
1
3
2 3 5

SAMPLE OUTPUT
4

Explanation

Xor of Subset of [2,3,5] are:
xor{0}=0,
xor{2}=2,
xor{3}=3,
xor{5}=5,
xor{2,3}=1,
xor{3,5}=6,
xor{2,5}=7,
xor{2,3,5}=4
Now,total no of distinct prime numbers are 4 i.e 2,3,5,7

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