A positive integer is called composite if it can be represented as a product of two positive integers, both greater than 11 . For example, the following numbers are composite: 66 , 44 , 120120 , 2727 . The following numbers aren't: 11 , 22 , 33 , 1717 , 9797 .
Alice is given a sequence of nn composite numbers a1,a2,…,ana1,a2,…,an .
She wants to choose an integer m≤11m≤11 and color each element one of mm colors from 11 to mm so that:
for each color from 11 to mm 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 11 , i.e. gcd(ai,aj)>1gcd(ai,aj)>1 for each pair i,ji,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 mm colors for each of the indices from 11 to nn .
Alice showed already that if all ai≤1000ai≤1000 then she can always solve the task by choosing some m≤11m≤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 mm from 11 to 1111 .
Input
The first line contains a single integer tt (1≤t≤10001≤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 nn (1≤n≤10001≤n≤1000 ) — the amount of numbers in a sequence aa .
The second line of the test case contains nn composite integers a1,a2,…,ana1,a2,…,an (4≤ai≤10004≤ai≤1000 ).
It is guaranteed that the sum of nn over all test cases doesn't exceed 104104 .
Output
For each test case print 22 lines. The first line should contain a single integer mm (1≤m≤111≤m≤11 ) — the number of used colors. Consider colors to be numbered from 11 to mm . The second line should contain any coloring that satisfies the above conditions. Print nn integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤m1≤ci≤m ), where cici is the color of the ii -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 mm from 11 to 1111 .
Remember that each color from 11 to mm 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 11 ).
Example
Input
Copy
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
Copy
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
每次遇到偏数学题都死得很惨==一开始差不多找到思路了后来又被gcd绕进去了（裂开
首先，观察到对于1e3的范围m最大为11肯定能满足，那么11这个数是怎么来的呢？就是平方小于1000的素数总共有11个：2，3，5，7，11，13，17，19，23，29，31 有数学知识可得：一个合数的最小质因子一定小于该合数的根号，那么1000以内的数的因子里都或多或少包含着这一个或几个素数，gcd不为1的话才能涂同种颜色，则对于每个数，直接对应到这11个质数里的某个数即可，一个素数对应的集合里涂同种颜色就行了。注意最终的输出要求1~m至少出现一次，所以得离散化一下（我选择map）
#include <bits/stdc++.h> using namespace std; int a[1005],n; int prime[12]={0,2,3,5,7,11,13,17,19,23,29,31};//11个素数 平方不超过1000 int chose[1005]={0}; int main() { int t; cin>>t; while(t--) { cin>>n; int i,j; memset(chose,0,sizeof(chose)); map<int,int>mp; for(i=1;i<=n;i++) { scanf("%d",&a[i]); for(j=1;j<=11;j++) { if(a[i]%prime[j]==0) { a[i]=prime[j]; chose[prime[j]]=1; } } } int cnt=1; for(i=1;i<=11;i++) { if(chose[prime[i]]) { mp[prime[i]]=cnt; cnt++; } } cout<<mp.size()<<endl; for(i=1;i<=n;i++)cout<<mp[a[i]]<<' '; cout<<endl; } }