Bình có một mảng \(a\) gồm \(n\) phần tử chính là một trong các hoán vị bất kỳ của \(n\) phần tử: \(1,2,3,...n\) với \(n\) là số nguyên dương.
Mỗi lần xoá, Bình chỉ xoá được số ở vị trí đầu tiên hoặc vị trí cuối cùng của mảng.
Hỏi Bình cần xoá ít nhất bao nhiêu lần để số \(1\) và số \(n\) không còn tồn tại trong mảng \(a\).

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) block tiếp theo, mỗi block có dạng như sau:
  ++ Dòng thứ nhất chứa số nguyên dương \(n(2\le n\le 100)\)
  ++ Dòng thứ hai chính là mảng \(a\)

Output

• Ứng với mỗi giá trị của testcase, hãy in kết quả ra màn hình.

Example

1
5
1 5 4 3 2

2