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