There is a new in-place sorting algorithm on the market, called swapsort. It can intelligently figure out how to sort an array of $n$ numbers into non-decreasing order efficiently using advanced logic. However there is a drawback: some arrays can't be sorted using this algorithm. The reason is the following: the only kind of swaps allowed are swaps of elements where at least one of them is a perfect square. In the case that the sorting can happen, this algorithm promptly gives you a sequence of allowed swaps, which upon executing make the array sorted. It is so efficient that it does not need more than $2n$ swaps to achieve this. However in the case that the array can't be sorted, it returns -1.

You have been given the job of simulating swapsort verbatim, and thus you need to do the following: given an integer $n$, and an array $a_1, ..., a_n$, you need to check whether swapsort can sort the array or not. If it can't, print -1. Otherwise print the number of swaps, and for each swap, in a new line, print the 0-based indices you intend to swap in that step.

Input format:

The input consists of $t$ test cases.
The first line contains $t$, where $t \le 10$.
Then $t$ test cases follow.
The first line of every test case contains an integer $n$ such that $1 \le n \le 10^5$
The next line contains $n$ space separated integers $a_i,\, 0 \le a_i \le 10^5$

Output format:

As in the problem statement

Time limit: 1s

Problem author: Navneel Singhal