## 24 hour archive: Problem

###
** 3262
- Find the Next Number** ** 3262 - Find the Next Number** ** 3262 - Find the Next Number**

#### Description

You are given a list of N numbers which are conveniently numbered from 1 to N (from left to right), and you must find for each element in the list the first number to the right which is co-prime with it. Let us call two positive integers (say, A and B, for example) co-prime if (and only if) their greatest common divisor is 1. (I.e. A and B are co-prime if GCD_ (A, B) = 1).

#### Input specification

The first line contain an integer number T no greater than 10^2 corresponding to the number of cases to process. The next T lines contains an integer number 1 <= N <= 10^4 representing the amount of elements in the list, followed by N space-separated positive integer numbers no greater than 10^2 (the elements of the list itself). You can safely assume that sum of all given values for N will not exceed 5*10^5.

#### Output specification

For each case output a line with N space-separated integer numbers not greater than N representing respective position of the solution for each element in the list. You must print first the solution for the first element, then the solution for the second element, and so on. If there is no solution for some element/position in the list you must print -1 instead (note that the last number must be always -1).

#### Sample input

`3`

1 17

5 1 2 3 5 7

9 60 12 18 5 35 7 14 21 11

#### Sample output

`-1`

2 3 4 5 -1

6 4 4 6 9 9 9 9 -1