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ữ 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

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\).

Example

2
3
1 2 3
4
1 1 1 1

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

Giới hạn

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