vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A positive integer is called composite if it can be represented as a product of two positive integers, both greater than 1. For example, the following numbers are composite: 6, 4, 120, 27. The following numbers aren't: 1, 2, 3, 17, 97.

Alice is given a sequence of n composite numbers a_1,a_2,…,a_n.

She wants to choose an integer m ≤ 11 and color each element one of m colors from 1 to m so that:

  * for each color from 1 to m there is at least one element of this color; 
  * each element is colored and colored exactly one color; 
  * the greatest common divisor of any two elements that are colored the same color is greater than 1, i.e. \gcd(a_i, a_j)>1 for each pair i, j if these elements are colored the same color. 



Note that equal elements can be colored different colors — you just have to choose one of m colors for each of the indices from 1 to n.

Alice showed already that if all a_i ≤ 1000 then she can always solve the task by choosing some m ≤ 11.

Help Alice to find the required coloring. Note that you don't have to minimize or maximize the number of colors, you just have to find the solution with some m from 1 to 11.

Input

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

The first line of the test case contains a single integer n (1 ≤ n ≤ 1000) — the amount of numbers in a sequence a.

The second line of the test case contains n composite integers a_1,a_2,…,a_n (4 ≤ a_i ≤ 1000).

It is guaranteed that the sum of n over all test cases doesn't exceed 10^4.

Output

For each test case print 2 lines. The first line should contain a single integer m (1 ≤ m ≤ 11) — the number of used colors. Consider colors to be numbered from 1 to m. The second line should contain any coloring that satisfies the above conditions. Print n integers c_1, c_2, ..., c_n (1 ≤ c_i ≤ m), where c_i is the color of the i-th element. If there are multiple solutions then you can print any of them. Note that you don't have to minimize or maximize the number of colors, you just have to find the solution with some m from 1 to 11.

Remember that each color from 1 to m should be used at least once. Any two elements of the same color should not be coprime (i.e. their GCD should be greater than 1).

Example

Input


3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961


Output


1
1 1 1
2
2 1
11
4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6

Note

In the first test case, \gcd(6,10)=2, \gcd(6,15)=3 and \gcd(10,15)=5. Therefore, it's valid to color all elements the same color. Note that there are other colorings which satisfy Alice's requirement in this test case.

In the second test case there is only one element of each color, so the coloring definitely satisfies Alice's requirement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As Harry wants to know about the sorcerer's stone, he went to the Mirror of Erised and asked him ,"where is the stone?". The mirror put a condition that harry must answer a question first then he will tell about the stone.The mirror asked him to tell the maximum length of a stream of two strings, each of length N, consisting of alphabets only.  Furthermore , the mirror defined him stream as a subset of string in order. For example,
"abc","aeg",.. etc are streams of string "abcdefg".

Input:
First line of input contains number of Test Cases T.
Each test case starts with an integer N, size of two strings.
Next two lines contains N alphabets each.

Output:
For each test case print one integer, the maximum length of stream between the two strings.

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

SAMPLE INPUT
2
2
ab
ba
3
abc
acb

SAMPLE OUTPUT
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr Leicester's cheese factory is the pride of the East Midlands, but he's feeling a little blue. It's the time of the year when **the taxman is coming round to take a slice of his cheddar** - and the final thing he has to work out is how much money he's spending on his staff. Poor Mr Leicester can barely sleep he's so stressed. Can you help? 

- Mr Leicester **employs 4 staff**, who together make **10 wheels of cheese every 6 minutes**.
- Worker pay is calculated on **how many wheels of cheese they produce in a day**. 
- Mr Leicester pays his staff according to the UK living wage, which is currently **£8.75p an hour**. There are **100 pence (p) to the UK pound (£)**. 

The input for function payCheese will be provided as an array of five integers, one for each amount of cheese wheels produced each day.

When the workforce don't work a nice integer number of minutes - much to the chagrin of the company accountant - Mr Leicester very generously **rounds up to the nearest hour** at the end of the week (*not the end of each day*). Which means if the workers make 574 wheels on each day of the week, they're each paid 29 hours for the week (28.699 hours rounded up) and not 30 (6 hours a day rounded up * 5).

The return value should be a string (with the £ included) of the **total £ of staff wages for that week.**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Прошло много лет, и на вечеринке снова встретились n друзей. С момента последней встречи техника шагнула далеко вперёд, появились фотоаппараты с автоспуском, и теперь не требуется, чтобы один из друзей стоял с фотоаппаратом, и, тем самым, оказывался не запечатлённым на снимке.

Упрощенно процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: в стоячем положении i-й из них занимает прямоугольник ширины w_{i} пикселей и высоты h_{i} пикселей. Но также, при фотографировании каждый человек может лечь, и тогда он будет занимать прямоугольник ширины h_{i} пикселей и высоты w_{i} пикселей.

Общая фотография будет иметь размеры W × H, где W — суммарная ширина всех прямоугольников-людей, а H — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография. Помогите им в этом.


-----Входные данные-----

В первой строке следует целое число n (1 ≤ n ≤ 1000) — количество друзей.

В последующих n строках следуют по два целых числа w_{i}, h_{i} (1 ≤ w_{i}, h_{i} ≤ 1000), обозначающие размеры прямоугольника, соответствующего i-му из друзей.


-----Выходные данные-----

Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.


-----Примеры-----
Входные данные
3
10 1
20 2
30 3

Выходные данные
180

Входные данные
3
3 1
2 2
4 3

Выходные данные
21

Входные данные
1
5 10

Выходные данные
50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Voritex a big data scientist collected huge amount of big data having structure of two rows and n columns.
Voritex is storing all the valid data for manipulations and pressing invalid command when data not satisfying the constraints.
Voritex likes brute force method and he calls it as BT, he decided to run newly created BT engine for getting good result.
At each instance when BT engine is outputting a newly created number Voritex calls it as BT number.
Voritex is daydreaming and thinking that his engine is extremely optimised and will get an interview call in which he will be explaining the structure of BT engine and which will be staring from 1 and simultaneously performing $i$-th xor operation with $i$ and previously(one step before) obtained BT number.
BT engine is outputting the $K$-th highest BT number in the first $N$ natural numbers.
Chef : (thinking) I also want to create BT engine……..

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of T test cases follows.
- The line of each test case contains a two integers $N$ and $K$.

-----Output:-----
For each test case, print a single line containing integer $K$-th highest number else print -$1$ when invalid command pressed.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq N \leq 100000$
- $1 \leq K \leq N$

-----Sample Input:-----
2
4 2
5 5

-----Sample Output:-----
2
0

-----EXPLANATION:-----
For first valid constraints generating output as 0 2 1 5 
1^1 first BT number is 0
2^0 second BT number is 2
3^2 third BT number is 1
4^1 fourth BT number is 5
Hence the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody is worried about Rakesh as the boy does not have much knowledge about the real world. He can not go from one place to another on his own. It's high time he learned to explore the city. He is going to a relative's house situated on the other side of the city on his own. As this is his first time, he is carrying a GPS tracker of a special kind. The tracker continuously sends information to the family of Rakesh about his movement. The information is sent using the following four letters: U, D, R, and L. Those letters indicate the moves taken by Rakesh. 

The city can be considered as a grid. Rakesh starts his journey from (0, 0) position of the grid. His relative's house is situated at (Rx, Ry). Rakesh can move in four directions: up, down, right, or left indicated by U, D, R, and L respectively. 

Any position of the city with x ordinate negative or greater than M is considered as dangerous. Also, any position of the city with y ordinate negative or greater than N is considered as dangerous. You will be given the total sequence of Rakesh's movement. You need to determine if Rakesh ended up being at his relative's house, at a dangerous place, or at a random place in the city.

To make things clear,

-  U indicates a move that increases position along y-axis by 1 
-  D indicates a move that decreases position along y-axis by 1 
-  R indicates a move that increases position along x-axis by 1 
-  L indicates a move that decreases position along x-axis by 1 

Note that we are interested in the position of Rakesh at the end of his journey only. He may visit some dangerous place or his relative's house at some intermediate point but that won't affect the answer.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of each test case follows.

- The first line of each test case contains two integers M and N.
- The second line contains two integers Rx and Ry.
- The third line contains the length of Rakesh's move sequence.
- The next line contains the move sequence containing letters U, D, R, and L only with no space.

-----Output-----
For each test case, print "Case i: ", and then the answer, where i is the testcase number, 1-indexed. The answer should be any of the following three strings:
-  "REACHED" if Rakesh could reach his relative's house 
-  "DANGER" if Rakesh ended up being in a dangerous place 
-  "SOMEWHERE" if Rakesh ended up being in somewhere safe place in the city other than his relative's place 
Don't print any quotation mark. Check the sample output.

-----Constraints-----

- 1 ≤ T ≤ 10
- 0 ≤ M, N ≤ 10000
- 0 ≤ Rx ≤  M 
- 0 ≤ Ry ≤  N 
- 0 ≤ Sum of the lengths of all sequences ≤ 10000

-----Example-----
Input:
2
20 20
4 5
13
LLUUUUURRRRRR
10 10
3 4
7
UDUDDRR

Output:
Case 1: REACHED
Case 2: DANGER

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Given a string `str`, find the shortest possible string which can be achieved by adding characters to the end of initial string to make it a palindrome.

# Example

 For `str = "abcdc"`, the output should be `"abcdcba"`.

# Input/Output


 - `[input]` string `str`

    A string consisting of lowercase latin letters.

    Constraints: `3 ≤ str.length ≤ 10`.


 - `[output]` a string

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Not Equal on a Segment

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given array *a* with *n* integers and *m* queries. The *i*-th query is given with three integers *l**i*,<=*r**i*,<=*x**i*.

For the *i*-th query find any position *p**i* (*l**i*<=≤<=*p**i*<=≤<=*r**i*) so that *a**p**i*<=≠<=*x**i*.

Input Specification:
The first line contains two integers *n*,<=*m* (1<=≤<=*n*,<=*m*<=≤<=2·105) — the number of elements in *a* and the number of queries.

The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106) — the elements of the array *a*.

Each of the next *m* lines contains three integers *l**i*,<=*r**i*,<=*x**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*,<=1<=≤<=*x**i*<=≤<=106) — the parameters of the *i*-th query.

Output Specification:
Print *m* lines. On the *i*-th line print integer *p**i* — the position of any number not equal to *x**i* in segment [*l**i*,<=*r**i*] or the value <=-<=1 if there is no such number.

Demo Input:
['6 4\n1 2 1 1 3 5\n1 4 1\n2 6 2\n3 4 1\n3 4 2\n']

Demo Output:
['2\n6\n-1\n4\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input contains two integers *a*,<=*b* (1<=≤<=*a*<=≤<=10,<=0<=≤<=*b*<=≤<=22·*a*<=-<=1) separated by a single space.

Output Specification:
Output two integers separated by a single space.

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

Demo Output:
['0 0\n', '3 0\n', '12 12\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The New Year holidays are over, but Resha doesn't want to throw away the New Year tree. He invited his best friends Kerim and Gural to help him to redecorate the New Year tree.

The New Year tree is an undirected tree with n vertices and root in the vertex 1.

You should process the queries of the two types:

  1. Change the colours of all vertices in the subtree of the vertex v to the colour c. 
  2. Find the number of different colours in the subtree of the vertex v. 

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 4·105) — the number of vertices in the tree and the number of the queries.

The second line contains n integers ci (1 ≤ ci ≤ 60) — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the vertices of the j-th edge. It is guaranteed that you are given correct undirected tree.

The last m lines contains the description of the queries. Each description starts with the integer tk (1 ≤ tk ≤ 2) — the type of the k-th query. For the queries of the first type then follows two integers vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — the number of the vertex whose subtree will be recoloured with the colour ck. For the queries of the second type then follows integer vk (1 ≤ vk ≤ n) — the number of the vertex for which subtree you should find the number of different colours.

Output

For each query of the second type print the integer a — the number of different colours in the subtree of the vertex given in the query.

Each of the numbers should be printed on a separate line in order of query appearing in the input.

Examples

Input

7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3


Output

2
3
4
5
1
2


Input

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


Output

6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monique and Paul both enjoy math and programming a lot. A few days ago they decided to compete against each other in many kinds of problem solving competitions. They solved hundreds of problems, but they still have not decided who the winner is, because the current score is surprisingly a draw. Monique gets impatient, and proposed a final game to decide the battle between them. The game is played as follows:

First, Monique constructs a tree with N nodes and binary weights on the edges of the tree. The weights are not known initially, but the structure of the tree is. After that, she writes down a list of Q distinct queries of the form:

query(v, u) - returns a parity of the sum of values on edges on the path from node v to node u in the tree. Each query has assigned a cost c_{v, u} denoting the cost of asking that query. 

Finally, she gives Paul two days to find the number of subsets S of the set of all queries such that after asking all queries from S, Paul can be sure what values are assigned to all edges of the tree Monique constructed and that the sum of costs of queries in S is the lowest from all such subsets. Since this number can be very large, Paul has to return it modulo 10^9 + 7.

The task is to help Paul solve the problem, so he can defeat Monique. 

Input format:

In the first line there are two space separated integers N and Q denoting the number of nodes in the tree and the number of all possible queries. In each of the next N - 1 lines there are two space separated integers v, u denoting that there is an edge between nodes v and u in the tree. In each of the following Q lines there are three space separated integers v, u, c_{v, u} denoting a single queries query(u, v), where c_{v,u} is the cost of asking the query.

Constraints:

2 ≤q N ≤q 75
1 ≤q Q ≤q N \cdot (N - 1) / 2
1 ≤q v, u ≤q N
v \neq u 
1 ≤q c_{v,u} ≤q 10^5
all queries in the input are distinct

Output format:

In a single line output a single integer denoting the answer to the problem.

SAMPLE INPUT
4 3
1 2
1 3
1 4
2 3 1
4 2 1
1 2 2

SAMPLE OUTPUT
1

Explanation

In the sample, the tree Monique created looks like this:

    2  
    |  
    1
  /   \  
 3     4

She gives 3 queries possible to ask:
query(2, 3) with cost 1  
query(4, 2) with cost 1  
query(1, 2) with cost 2 

The best Paul can do is to ask all available queries with total cost equal to 1 + 1 + 2 = 4. 

After asking the third query, Paul knows the value assigned to edge (1, 2). After that, if he asks the first query, he can figure out the value assigned to edge (1, 3). Finally, after asking the second query, he can figure out the value assigned to edge (1, 4). It is not possible to figure out values assigned to all edges asking a different set of queries with lower cost. It follows that there is only one subset of all queries with the lowest total cost, such that the queries in this set are sufficient to figure out values assigned to all the edges.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: A Map of the Cat

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
If you have ever interacted with a cat, you have probably noticed that they are quite particular about how to pet them. Here is an approximate map of a normal cat.

However, some cats won't tolerate this nonsense from the humans. Here is a map of a grumpy cat.

You have met a cat. Can you figure out whether it's normal or grumpy?

Input Specification:
none

Output Specification:
none

Note:
Please make sure to use the stream flushing operation after each query in order not to leave part of your output in some buffer.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems. 

Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates. The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square. 

Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.

Input Specification:
The first line of the input contains number *n* — the number of mines on the map (2<=≤<=*n*<=≤<=1000). Each of the next *n* lines contains a pair of integers *x**i* and *y**i* — the coordinates of the corresponding mine (<=-<=109<=≤<=*x**i*,<=*y**i*<=≤<=109). All points are pairwise distinct.

Output Specification:
Print the minimum area of the city that can cover all the mines with valuable resources.

Demo Input:
['2\n0 0\n2 2\n', '2\n0 0\n0 3\n']

Demo Output:
['4\n', '9\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw $n$ squares in the snow with a side length of $1$. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length $1$, parallel to the coordinate axes, with vertices at integer points.

In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends $(x, y)$ and $(x, y+1)$. Then Sofia looks if there is already a drawn segment with the coordinates of the ends $(x', y)$ and $(x', y+1)$ for some $x'$. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates $x$, $x+1$ and the differing coordinate $y$.

For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:  [Image] 

After that, she can draw the remaining two segments, using the first two as a guide:  [Image] 

If Sofia needs to draw two squares, she will have to draw three segments using a ruler:  [Image] 

After that, she can draw the remaining four segments, using the first three as a guide:  [Image] 

Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.


-----Input-----

The only line of input contains a single integer $n$ ($1 \le n \le 10^{9}$), the number of squares that Sofia wants to draw.


-----Output-----

Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw $n$ squares in the manner described above.


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

Output
2

Input
2

Output
3

Input
4

Output
4

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