Alice có ~N~ bình nước giống nhau, mỗi bình có thể chứa được ~V~ lít nước. Hiện tại, bình thứ ~i~ (~1 \le i \le N~) chứa ~v_i~ lít nước (~v_1 + v_2 + \dots + v_N = V~). Alice muốn thực hiện một dãy các lần đổ nước giữa các bình để số lượng bình rỗng là nhiều nhất. Mỗi lần cô có thể đổ nước từ bình ~i~ sang bình ~j~ nếu ~v_i \ge v_j~ một lượng nước bằng ~v_j~ lít, sau khi đổ bình ~i~ còn ~v_i - v_j~ lít, bình ~j~ có ~2v_j~ lít.

Yêu cầu: Hãy tìm một dãy các lần đổ nước để số bình rỗng là nhiều nhất.

Input

Dòng đầu chứa số nguyên ~T~ (~T \le 10~) là số bộ dữ liệu, tiếp theo là các nhóm dòng, mỗi nhóm có khuôn dạng:

• Dòng đầu của nhóm chứa số nguyên dương ~N~ (~2 \le N \le 10~).

• Dòng thứ hai của nhóm chứa ~N~ số nguyên dương ~v_1, v_2, \dots, v_N~ (~v_1 + v_2 + \dots + v_N = V \le 10^{12}~).

Output

Gồm ~T~ nhóm dòng, mỗi nhóm mô tả lời giải tương ứng một bộ dữ liệu theo khuôn dạng:

• Dòng đầu ghi số nguyên ~S~ là số lần đổ nước;

• Dòng thứ ~t~ (~1 \le t \le S~) trong ~S~ dòng sau, mỗi dòng ghi hai số ~i, j~ cho biết lần đổ thứ ~t~ đổ nước từ bình ~i~ sang bình ~j~.

Scoring

Sample Input 1

2
3
1 2 3
4
1 1 1 1

Sample Output 1

2
3 1
2 1
3
2 3
1 4
4 3

Notes

• Với bộ dữ liệu thứ nhất có thể nhận được 1 bình rỗng. ~(1, 2, 3) \to (2, 2, 2) \to (2, 0, 4)~

• Với bộ dữ liệu thứ hai có thể nhận được 3 bình rỗng. ~(1, 1, 1, 1) \to (2, 0, 2, 0) \to (4, 0, 0, 0)~