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ố lượng bình rỗng là nhiều nhất.

Input

Dữ liệu vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• 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 chứa số nguyên dương ~N~ (~2 \le N \le 10~).
  • Dòng thứ hai 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

Kết quả ghi ra thiết bị ra chuẩn (màn hình) 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~.

Ràng buộc

• Subtask 1 (20%): ~N = 3~ và ~V \le 300~.
• Subtask 2 (20%): ~N = 3~ và ~V \le 3000~.
• Subtask 3 (20%): ~V \le 3000~.
• Subtask 4 (20%): ~N = 3~.
• Subtask 5 (20%): Không có ràng buộc nào thêm.

Ví dụ

Input

2
3
1 2 3
4
1 1 1 1

Output

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

Giải thích:

• 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)~. ```