Bé An rất thích xếp hình. Cậu có một hộp gồm \(n\) khối lập phương đủ màu sắc.
Các khối lập phương được đánh số từ \(1\) đến \(n\), khối thứ \(i\) được mô tả bởi hai thông số: màu \(c_i\) và kích thước \(s_i\).

Một Tháp Sọc được định nghĩa là một tòa tháp gồm các khối lập phương chỉ thuộc chính xác hai màu khác nhau.
Ngoài ra, các khối lập phương trong tháp phải được xếp sao cho màu xen kẽ nhau (tức hai khối kề nhau không được cùng màu).
Tháp phải có ít nhất hai khối lập phương.

Chiều cao của Tháp Sọc chính là tổng kích thước của tất cả khối lập phương trong tháp.
Hãy giúp bé An xây dựng một Tháp Sọc có chiều cao lớn nhất từ những khối lập phương có sẵn.

Input

Dòng đầu tiên chứa một số nguyên \(\theta\) là số lượng bộ dữ liệu. Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:

• Dòng đầu tiên là một dòng trống.
• Dòng thứ hai chứa một số nguyên \(n\) \((2 \le n \le 10^5)\) - số lượng khối lập phương.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(c_i\) và \(s_i\) \((1 \le c_i, s_i \le 10^9)\) -
  màu sắc và kích thước của khối lập phương thứ \(i\).

Dữ liệu đảm bảo luôn có hai khối lập phương khác màu nhau.

Gọi \(\Sigma_n\) là tổng giá trị của \(n\) trong các bộ dữ liệu của một test. Dữ liệu đảm bảo \(\Sigma_n \leq 5 \cdot 10^5\).

Output

Với mỗi bộ dữ liệu, hãy in ra mô tả của Tháp Sọc có chiều cao lớn nhất theo định dạng sau:

• Dòng đầu tiên chứa chiều cao của tháp.
• Dòng thứ hai chứa số lượng khối lập phương tạo thành tháp.
• Dòng thứ ba chứa các chỉ số của những khối lập phương theo thứ tự từ dưới lên trên.

Nếu tồn tại nhiều Tháp Sọc có chiều cao lớn nhất, bạn có thể in ra bất kỳ tháp nào trong số đó.

Scoring

• Subtask \(1\) (\(20\) điểm): \(n \le 100\) và \(\Sigma_n \leq 500\)
• Subtask \(2\) (\(30\) điểm): \(n \le 1000\) và \(\Sigma_n \leq 5000\)
• Subtask \(3\) (\(50\) điểm): Không có ràng buộc gì thêm.

Example

3

2
1 6
2 7

3
1 10
2 15
2 17

4
1 1
2 2
3 3
4 4

13
2
1 2 
42
3
3 1 2 
7
2
3 4