You are given a sequence {`A`_{1}, `A`_{2}, ..., `A`_{N}}. You task is to change all the element of the sequence to 1 with the following operations (you may need to apply it multiple times):

- choose two indexes
`i`and`j`(1 ≤`i`<`j`≤`N`); - change both
`A`_{i}and`A`_{j}to gcd(`A`_{i},`A`_{j}), where gcd(`A`_{i},`A`_{j}) is the greatest common divisor of`A`_{i}and`A`_{j}.

You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5`N` operations.

Input will consist of multiple test cases.

The first line of each case contains one integer `N` (1 ≤ `N` ≤ 10^{5}), indicating the length of the sequence. The second line contains `N` integers, `A`_{1}, `A`_{2}, ..., `A`_{N} (1 ≤ `A`_{i} ≤ 10^{9}).

For each test case, print a line containing the test case number (beginning with 1) followed by one integer `M`, indicating the number of operations needed. You must assure that `M` is no larger than 5`N`. If you cannot find a solution, make `M` equal to -1 and ignore the following output.

In the next `M` lines, each contains two integers `i` and `j` (1 ≤ `i` < `j` ≤ `N`), indicating an operation, separated by one space.

If there are multiple answers, you can print any of them.

Remember to print a blank line after each case. But extra spaces and blank lines are not allowed.

提交代码