Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given an integer n and an array C of size n. Your task is to construct another array A of size n such that:

1. Each value in A is in the range [\(1, 10^9\)].
2. For each i (1 ≤ i ≤ n) and any j (i ≤ j ≤ n), if i and j share the same Smallest Prime Factor(SPF) (Ex. SPF(i)=SPF(j)), then the count of indices j where A[i] > A[j] must be exactly C[i].
3. If multiple valid arrays A exist, you can print any of them.
4. If it is impossible to construct such an array, print "NO".

• Smallest Prime Factor (SPF) means, smallest prime number which is divisble by this number. For example, SPF(4)= 2, SPF(5)= 5, SPF(6)= 2, SPF(9)= 3, SPF(25)=5 etc.
• Since 1 have no prime factor, we should consider SPF(1)=1.

Input

• The first line contains a single integer t (1 ≤ t ≤ \(10^3\))—the number of test cases.
• Each test case consists of:
  • A single integer n (1 ≤ n ≤ 5 × \(10^5\))—the size of the array.
  • A line containing n space-separated integers \(C_1, C_2, ..., C_n\) (0 ≤ \(C_i\) ≤ n)..
• Sum of n overall test cases doesn't exceed \(5 * 10^5\)

Output

For each test case:

• If a valid array A exists, print "YES" followed by n space-separated integers representing A.
• Otherwise, print "NO"
• Note : The output is case insensitive, meaning you may print "YES", "yes", "YeS", etc., and it will be considered correct.

Sample

2
5
0 1 0 0 0
4
0 1 1 1

YES
10 30 16 12 13 
No

First Test case :
Consider Second index ,i = 2, \(C_2\)=1, There must be an index j( i<= j <=n), where SPF(i)=SPF(j) and A[i] > A[j].
Only j=4, full fill above conditions.
i=2 and j=4, SPF(i)=SPF(2)=2, SPF(j)=SPF(4)=2.
Since SPF(i)=SPF(j) and A[i]>A[j] (30 > 12). So \(C_2=1\).