Vào năm 2077, việc ra đề trở nên rất đơn giản. Robot sẽ tạo ra một bài toán bằng cách thiết lập một số phép toán ngẫu nhiên rồi tự giải nó. Người ra đề chỉ cần kiểm tra xem bài toán đó có đúng hay không.

Dưới đây là một bài toán từ năm 2077:

Cho một hoán vị $p_1, p_2, \dots, p_n$, đảm bảo rằng $n$ là số chẵn. Bạn muốn sắp xếp hoán vị này bằng cách chỉ sử dụng một loại thao tác duy nhất:

• FakeSort(l,r): Bạn phải đảm bảo rằng $r - l + 1$ là số chẵn. Đặt $k = r - l + 1$, khi đó $k/2$ phần tử lớn nhất và $k/2$ phần tử nhỏ nhất trong dãy con liên tiếp $p_l, p_{l+1}, \dots, p_r$ sẽ được sắp xếp độc lập với nhau. Cụ thể, gọi $L_1, L_2, \dots, L_{k/2}$ là chỉ số của $k/2$ số lớn nhất, và $S_1, S_2, \dots, S_{k/2}$ là chỉ số của $k/2$ số nhỏ nhất. Trước tiên chúng ta sắp xếp các số tại các chỉ số $L_1 \sim L_{k/2}$, sau đó sắp xếp các số tại các chỉ số $S_1 \sim S_{k/2}$.

Đây là một ví dụ cụ thể; giả sử hoán vị là $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Nếu chúng ta gọi FakeSort(2,7):

• $k = r - l + 1 = 6$. Dãy con liên tiếp $p_l, p_{l+1}, \dots, p_r$ là $\{5, 7, 1, 8, 6, 4\}$; chúng ta sẽ sắp xếp $3$ số lớn nhất và $3$ số nhỏ nhất của dãy này một cách độc lập.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; $3$ số lớn nhất được in đậm. Sau khi sắp xếp, chúng trở thành $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; $3$ số nhỏ nhất được in đậm. Sau khi sắp xếp, chúng trở thành $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Vì vậy, $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ sau khi thực hiện FakeSort(2,7) sẽ trở thành $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Hãy sử dụng không quá $114$ thao tác để sắp xếp hoán vị hoặc xác định rằng điều đó là không thể. Có thể chứng minh rằng nếu một hoán vị có thể được sắp xếp bằng thao tác này, thì luôn tồn tại cách sử dụng không quá $114$ thao tác.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^3$), là số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa một số nguyên chẵn $n$ ($4 \le n \le 10^5$), là độ dài của hoán vị.

Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), là hoán vị mà bạn cần sắp xếp. Đảm bảo rằng $p$ là một hoán vị.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ test, nếu không thể sắp xếp hoán vị, hãy in ra $-1$.

Ngược lại, hãy in ra một số nguyên $k$ ($0 \le k \le 114$), biểu thị số lượng thao tác được sử dụng.

Trong $k$ dòng tiếp theo, mỗi dòng in ra $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ là số chẵn), biểu thị việc thực hiện FakeSort(l,r).

Ví dụ

Dữ liệu vào mẫu 1

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

Kết quả mẫu 1

1
1 4
-1
2
4 7
1 6