human
Can you provide a Python program to find the required coloring given the following:
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...
Solve the task in PYTHON.
assistant
#Here is Python program to find the required coloring.

"""Template for Python Competitive Programmers prepared by Mayank Chaudhary """

# to use the print and division function of Python3
from __future__ import division, print_function

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""use resource"""
# import resource
# resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])

"""for factorial"""

# def prepare_factorial():
#     fact = [1]
#     for i in range(1, 100005):
#         fact.append((fact[-1] * i) % mod)
#     ifact = [0] * 100005
#     ifact[100004] = pow(fact[100004], mod - 2, mod)
#     for i in range(100004, 0, -1):
#         ifact[i - 1] = (i * ifact[i]) % mod
#
#     return fact, ifact

"""uncomment next 4 lines while doing recursion based question"""
# import threading
# threading.stack_size(2**27)
import sys
# sys.setrecursionlimit(10**6)

"""uncomment modules according to your need"""
# from bisect import bisect_left, bisect_right, insort
# import itertools
from math import floor, ceil, sqrt
# import heapq
# from random import randint as rn
# from Queue import Queue as Q
# from collections import Counter, defaultdict

'''
def modinv(n, p):
    return pow(n, p - 2, p)
'''

# def ncr(n, r,  fact, ifact):  # for using this uncomment the lines calculating fact and ifact
#     t = ((fact[n]) * (ifact[r] % mod)) % mod
#     return t


def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()

# def GCD(x, y):
#     while (y):
#         x, y = y, x % y
#     return x
#
# def lcm(x, y):
#     return (x*y)//(GCD(x, y))
#
# def get_xor(n):
#     return [n,1,n+1,0][n%4]

"""*******************************************************"""

def prime_sieve(n):
    """returns a sieve of primes >= 5 and < n"""
    flag = n % 6 == 2
    sieve = bytearray((n // 3 + flag >> 3) + 1)
    for i in range(1, int(n**0.5) // 3 + 1):
        if not (sieve[i >> 3] >> (i & 7)) & 1:
            k = (3 * i +...