Little Cyan Fish có một hoán vị $p_1, p_2, \ldots, p_n$ của các số nguyên từ $1$ đến $n$, và như tên bài toán gợi ý, cậu muốn sắp xếp nó theo thứ tự tăng dần. Lần này, thao tác mà cậu có thể thực hiện như sau.

• Trong một thao tác, Little Cyan Fish có thể chọn hai số nguyên $i$ và $j$ sao cho $1 \le i < j \le n$ và hoán đổi $p_i$ với $p_j$.

Nhưng thôi nào, ai cũng biết cách sắp xếp một hoán vị bằng các phép hoán đổi đơn giản, nên hiển nhiên đây không phải là điều bài toán yêu cầu bạn làm. Thay vào đó, Little Cyan Fish định nghĩa khoảng cách của một thao tác là $j - i$. Đối với một dãy thao tác sắp xếp được hoán vị, gọi $a_d$ là số lượng thao tác có khoảng cách $d$, với mọi $1 \le d < n$.

Trong tất cả các dãy thao tác hữu hạn sắp xếp được hoán vị, Little Cyan Fish muốn bạn tìm dãy $(a_1, a_2, \ldots, a_{n-1})$ nhỏ nhất theo thứ tự từ điển, và xây dựng một dãy gồm nhiều nhất $5n$ thao tác đạt được nó.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^6$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($2 \le n \le 10^6$), cho biết độ dài của hoán vị. Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), cho biết hoán vị đó. Dữ liệu đảm bảo rằng $p$ là một hoán vị có độ dài $n$.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra câu trả lời theo định dạng sau.

Dòng đầu tiên của mỗi bộ dữ liệu cần chứa $n - 1$ số nguyên $a_1, a_2, \ldots, a_{n-1}$, là dãy nhỏ nhất theo thứ tự từ điển.

Dòng thứ hai cần chứa một số nguyên duy nhất $k$ ($0 \le k \le 5n$), là số lượng thao tác trong dãy của bạn.

Mỗi dòng trong $k$ dòng tiếp theo cần chứa hai số nguyên $i$ và $j$ ($1 \le i < j \le n$), là các chỉ số được chọn trong thao tác tương ứng. Các thao tác khi được thực hiện theo đúng thứ tự đã cho phải sắp xếp được hoán vị đầu vào, và với mọi $1 \le d < n$, phải có đúng $a_d$ thao tác có khoảng cách $d$.

Có thể chứng minh rằng luôn tồn tại một dãy tối ưu gồm nhiều nhất $5n$ thao tác. Nếu có nhiều dãy thao tác hợp lệ, bạn có thể in ra bất kỳ dãy nào trong số đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0 1
1
1 3
0 1 2
3
1 4
2 4
1 4
0 3 2
5
1 3
1 4
2 4
1 4
1 3

Ghi chú

Ở bộ dữ liệu mẫu thứ nhất, Little Cyan Fish hoán đổi vị trí $1$ và $3$. Thao tác này sắp xếp hoán vị bằng một thao tác có khoảng cách $2$.

Ở bộ dữ liệu mẫu thứ hai, một dãy tối ưu là $(1, 4)$, $(2, 4)$, $(1, 4)$. Các khoảng cách lần lượt là $3$, $2$ và $3$, vì vậy dãy thu được là $(0, 1, 2)$.

Ở bộ dữ liệu mẫu thứ ba, một dãy tối ưu là $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Số lượng thao tác theo từng khoảng cách của nó là $(0, 3, 2)$.