3262 - Find the Next Number 3262 - Find the Next Number 3262 - Find the Next Number

Statistics Sub: 149 | AC: 38 | AC%: 25,50 | Score: 2,82
Created by Yonny Mondelo Hernández
Added by janton (2015-04-24)
Limits
Total Time: 10000 MS | Test Time: 2500 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

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).
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).
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.
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.
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).
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).
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.

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

Hint(s)




Recommendation

We have carefully selected several similar problems: 3379 | 3378 | 3377 | 2916 | 3954 | 3303