Given an Array \(arr\) of length \(N\) find the index (0-indexed) of previous co-prime element for each index \(0 \le i < N\), or \(-1\) if there's no such value.

Two values \(x\) and \(y\) are called co-prime if \(GCD(x, y) = 1\).

Previous co-prime element of \(arr[i]\) is the first element co-prime to \(arr[i]\) on the left of index \(i\), ie. maximum \(j\) such that \(GCD(arr[i], arr[j]) = 1\) and \(j < i\), or -1 if there's no co-prime element to the left of \(arr[i]\).

NOTE:

Use of Fast I/O is recommended for this problem.

Input Format:

First line contains an integer \(T\) denoting the number of test cases.
First line of each testcase contains an integer \(N\) denoting length of \(arr\).
Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).

Output Format:

For each testcase, In a single line, print the index of previous co-prime element of \(arr[i]\) for each index \(0 \le i < N\), or \(-1\) if no such value.

Constraints:

\(1 \le T \le 10\)
\(1 \le N \le 10^5\)
\(1 \le arr[i] \le 10^5\)