Bạn có một hoán vị: một mảng a = [a1, a2,…, an] gồm các số nguyên phân biệt từ 1 đến n. Độ dài của hoán vị n là số lẻ. Hãy xem xét thuật toán sắp xếp hoán vị theo thứ tự tăng dần sau đây. Thủ tục trợ giúp của thuật toán, f (i) , nhận một đối số duy nhất i (1≤i≤n − 1) và thực hiện như sau. Nếu ai> ai + 1, giá trị của ai và ai + 1 được trao đổi. Nếu không, hoán vị không thay đổi. Thuật toán bao gồm các lần lặp, được đánh số bằng các số nguyên liên tiếp bắt đầu bằng 1 . Trên tôi -lặp lại thứ, thuật toán thực hiện như sau:

nếu tôi là số lẻ, gọi f (1), f (3),…, f (n − 2) ;

nếu tôi là chẵn, gọi f (2), f (4),…, f (n − 1) .

Có thể chứng minh rằng sau một số lần lặp lại hữu hạn, hoán vị sẽ được sắp xếp theo thứ tự tăng dần. Sau bao nhiêu lần lặp lại điều này sẽ xảy ra lần đầu tiên?

Input:

Đầu vào Mỗi thử nghiệm chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm t (1≤t≤10 ^ 4 ). Sau đây là mô tả các trường hợp kiểm thử. Dòng đầu tiên của mỗi trường hợp kiểm tra chứa một số nguyên n (3≤n≤2⋅10 ^ 5−1; n là lẻ) - độ dài của hoán vị. Dòng thứ hai chứa n các số nguyên phân biệt a1, a2,…, an (1≤ai≤n ) - hoán vị chính nó. Đảm bảo rằng tổng của n trên tất cả các trường hợp thử nghiệm không vượt quá 2⋅10 ^ 5−1

Output:

. Đầu ra Đối với mỗi trường hợp thử nghiệm, in số lần lặp lại mà sau đó hoán vị sẽ được sắp xếp theo thứ tự tăng dần lần đầu tiên. Nếu hoán vị đã cho đã được sắp xếp, hãy in ra 0.

Input:

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

ouput:

3

5

0

Ghi chú Trong trường hợp thử nghiệm đầu tiên, hoán vị sẽ thay đổi như sau: sau 1 lần lặp -st: [2,3,1] ; sau 2 -nd lần lặp: [2,1,3] ; sau 3 -lặp lại thứ ba: [1,2,3] . Trong trường hợp thử nghiệm thứ hai, hoán vị sẽ thay đổi như sau: sau 1 lần lặp -st: [4,5,1,7,2,3,6] ; sau 2 -nd lần lặp: [4,1,5,2,7,3,6] ; sau 3 -lặp lại thứ ba: [1,4,2,5,3,7,6] ; sau 4 -lần lặp thứ: [1,2,4,3,5,6,7] ; sau 5 -lặp lại thứ: [1,2,3,4,5,6,7] . Trong trường hợp thử nghiệm thứ ba, hoán vị đã được sắp xếp và câu trả lời là 0 .

Bài 2. Cho tập hợp A = f1; 2; 3; · · · ; 2ng. Chứng minh rằng nếu ta lấy ra n + 1 số khác nhau từ tập A, luôn
có 2 số chia hết cho nhau.
Bài 3. Các số 1; 2; 3; · · · ; 2020 ban đầu được viết lên bảng theo một thứ tự bất kì. Ở mỗi bước, chọn 2 số bất
kì và đổi chỗ 2 số đó. Hỏi sau 6969 bước, ta có thể thu được dãy số viết ban đầu hay không?
Bài 4. Trên một đường tròn, ta viết 2 số 1 và 48 số 0 theo thứ tự 1; 0; 1; 0; 0; · · · ; 0. Mỗi phép biến đổi, ta
thay một 2 cặp 2 số liền nhau bất kì (x; y) bởi (x + 1; y + 1). Hỏi nếu ta lặp lại thao tác trên thì có thể đến 1
lúc nào đó thu được 50 số giống nhau hay không?
Bài 5. Trên đường tròn lấy theo thứ tự 12 điểm A1; A2; A3; · · · ; A12. Tại điểm A1 ta viết số -1, tại các đỉnh
còn lại ta viết số 1. Ở mỗi bước, chọn 6 điểm kề nhau bất kì và đổi dấu tất cả các số tại các điểm đó. Hỏi nếu
ta lặp lại thao tác trên thì có thể đến 1 lúc nào đó thu được trạng thái: điểm A2 viết số -1, các đỉnh còn lại
viết số 1, hay không?
Bài 6. Kí hiệu S(n) là tổng các chữ số của n. Tìm n, biết:
a) n + S(n) + S(S(n)) = 2019.
b) n + S(n) + S(S(n)) = 2020.
Bài 7. Giả sử (a1; a2; a3; · · · ; an) là 1 hoán vị của (1; 2; 3; · · · ; n) (là các số 1; 2; 3; · · · ; n nhưng viết theo
thứ tự tùy ý). Chứng minh rằng nếu n lẻ thì số P = (a1 - 1)(a2 - 2)(a3 - 3) · · · (an - n) là số chẵn.
Bài 8. Trên bàn có 6 viên sỏi, được chia thành vài đống nhỏ. Mỗi phép biến đổi được thực hiện như sau: ta
lấy ở mỗi đống 1 viên và lập thành đống mới. Hỏi sau 69 bước biến đổi như trên, các viên sỏi trên bàn được
chia thành mấy đống?
Bài 9. Xung quanh công viên người ta trồng n cây, giả sử trên mỗi cây có 1 con chim. Ở mỗi lượt, có 2 con
chim đồng thời bay sang cây bên cạnh theo hướng ngược nhau.
a) Với n lẻ, chứng tỏ rằng có thể có cách để tất cả các con chim cùng đậu trên một cây.
b) Chứng minh điều ngược lại với n chẵn.