조각 모으기

ad gkazalli corsines

— Feryquitous, 「Arcahv」

히카리는 $N$개의 조각을 모으려고 한다. 조각은 하늘을 떠다니고 있어 그냥 모을 수 없고, 땅에 떨어진 조각만 모을 수 있다. 처음에 $i$번째 조각의 높이는 $H_i$이고, $H_i = 0$이 되면 히카리는 $i$번째 조각을 모을 수 있다.

다행히, 히카리에게는 신비한 능력이 있어서 두 조각의 상호작용을 통해 그 중 한 조각의 높이를 낮출 수 있다. $H_a \geq \gcd(H_a,H_b)$인 서로 다른 두 정수 $a$, $b$ $(1 \leq a, b \leq N, a \ne b)$를 골라 능력을 사용할 경우 $H_a$를 $\gcd(H_a,H_b)$만큼 감소시킬 수 있다.

하지만, 능력을 너무 많이 사용하면 타이리츠에게 들키기 때문에 최대 $N + 40$번 이하로 능력을 사용해서 모든 조각을 땅으로 떨어뜨려야 한다.

히카리를 위해서 $N + 40$번 이하로 능력을 사용해서 모든 조각을 땅으로 떨어뜨리는 방법을 아무거나 하나 찾아야 한다. 그러한 방법이 주어진 제약조건 하에 항상 존재한다는 것을 증명 가능하다. 능력을 사용하는 횟수를 최소화할 필요는 없다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 5000)$

각 테스트 케이스의 첫 번째 줄에 히카리가 모아야 하는 조각의 개수 $N$이 주어진다. $(2 \le N \le 200\,000)$

각 테스트 케이스의 두 번째 줄에 각 조각의 높이를 나타내는 $N$개의 정수 $H_1,H_2,\dots H_N$이 공백을 사이에 두고 주어진다. $(0 \le H_i \le 10^6)$

모든 테스트 케이스의 $N$의 총합은 $200\,000$을 넘지 않는다.

각 테스트 케이스에 대해, 첫 번째 줄에 사용한 능력의 횟수 $K$를 출력한다. $(0 \leq K \leq N + 40)$

다음 $K$개의 줄 중 $i$번째 줄에 $i$번째로 능력을 사용할 때 선택한 $a, b$를 공백을 사이에 두고 출력한다.

가능한 정답이 여러 가지라면 그 중 아무거나 하나 출력한다.