Có ~n~ lỗ bi trên nằm cách đều nhau trên một đường tròn. Các lỗ được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Đồng thời, có một lỗ đựng bi nằm ở tâm đường tròn được đánh số ~n+1~.

Ban đầu, với ~n~ lỗ bi nằm trên đường tròn thì lỗ ~i~ chứa đúng một viên bi có màu ~a_i~, còn lỗ ~n+1~ là lỗ trống. Các viên bi có màu từ ~1~ đến ~n~, không có hai viên bi nào cùng màu. Bạn có thể di chuyển viên bi từ một lỗ đang chứa bi đến một lỗ trống nếu hai lỗ bi đó nằm liên tiếp nhau trên đường tròn, hoặc một trong hai lỗ bi là lỗ ~n+1~.

Hãy tìm dãy thao tác chuyển bi sao cho bi màu ~i~ về đúng với lỗ ~i~, đồng thời số thao tác không vượt quá ~1500~.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 50~). Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~3 \le n \le 50~) – số lỗ bi nằm trên đường tròn.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) – màu của viên bi nằm trên ~n~ lỗ bi nằm trên đường tròn. Dữ liệu vào đảm bảo mỗi màu bi sẽ xuất hiện đúng một lần.

Output

Với mỗi test case, hãy in ra đáp án theo định dạng như sau:

Dòng đầu tiên in ra số nguyên ~k~ (~0 \le k \le 1500~) – số thao tác di chuyển bi cần thực hiện.

Dòng thứ ~i~ trong ~k~ dòng tiếp theo in ra hai số nguyên ~s_i~ và ~t_i~ (~1 \le s_i, t_i \le n+1~, ~s_i \ne t_i~) mô tả thao tác di chuyển bi thứ ~i~ (từ lỗ ~s_i~ sang lỗ ~t_i~). Lỗ ~s_i~ phải chứa một viên bi, và lỗ ~t_i~ phải trống.

Có thể chứng minh rằng luôn tồn tại một cách di chuyển bi thỏa yêu cầu đề bài.

Scoring

Sample Input 1

2
3
2 3 1
3
1 2 3

Sample Output 1

4
3 4
2 3
1 2
4 1
0

Notes

Với test case thứ nhất, hình vẽ bên dưới minh họa một cách di chuyển bi thỏa yêu cầu đề bài. Số ghi bên ngoài lỗ bi cho biết số thứ tự của lỗ bi, số ghi bên trong cho biết màu của viên bi trong lỗ.

Với test case thứ hai, các viên bi đều đã ở đúng ô bi nên ta không cần thực hiện thao tác di chuyển bi nào.