human
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...
Using python3 can you solve the prior task?

Give me a Python program to find the required coloring?
assistant
#Here is Python program to find the required coloring.

debug = 0
if debug:
    print("DEBUG MODE ON")
    f = None
    def new_input():
        global f
        if f==None:
            f = open('input.txt')
        return f.readline()
    input = new_input
def readrange(): return range(int(input()))
def readint(): return int(input())
def readarr(): return [int(x) for x in input().split()]
def readmat(rows): return [readarr() for _ in range(rows)]

primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31)
for _ in readrange():
    input()
    arr = readarr()
    for k in range(len(arr)):
        arr[k] = min((p for p in primes if arr[k]%p == 0))
    colors = tuple(set(arr))
    print(len(colors))
    print(*[colors.index(element) + 1 for element in arr])