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:
Input Format:
Output Format:
Constraints:
In third testcase, \(arr = [3, 6, 9, 1, 2, 3]\)
First, Second and Third element has no co-prime element to left, hence \(-1\) is their previous index.
Fourth element is co-prime to \(9\), ie. index \(2\).
Fifth element is co-prime to \(1\), ie. index \(3\).
Sixth element is co-prime to \(2\), ie. index \(4\).