#127 조각 모으기

Statement

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)$ 만큼 감소시킬 수 있다.

$\gcd$ 의 정의

$\gcd(n,m)$ 은 $n,m \gt 0$ 일 경우 두 정수 $n$ , $m$ 을 나머지 없이 나눌 수 있는 가장 큰 양의 정수로 정의하며, 그 외에는 $\gcd(n,0) = \gcd(0,n) = n$ 으로 정의한다.

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

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

Input

첫 번째 줄에 테스트 케이스의 개수 $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$ 을 넘지 않는다.

Output

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

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

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

Samples

Input

Output