Có \(n\) con quỷ chiếm đóng các vùng đất khác nhau, mỗi con đều sở hữu một viên ngọc sức mạnh vô giá.

Vì không biết rõ sức mạnh thực sự của nhau, chúng quyết định cùng ký kết Giao Ước 666 dưới sự chứng giám của Chúa Quỷ. Con số 666 – biểu tượng của quyền lực và sự hỗn loạn – được chọn để khẳng định đây là lời thề bất khả phá vỡ: bất kể chuyện gì xảy ra, mỗi năm chúng sẽ phải trao đổi ngọc sức mạnh với nhau.

Nội dung giao ước quy định:

• Mỗi năm, nếu con quỷ \(i\) đang có ít nhất \(1\) viên ngọc, nó sẽ trao đúng 1 viên cho con quỷ \(r_i\) mà nó đã chỉ định trước.
• Nếu một con quỷ không có viên ngọc nào thì sẽ không làm gì cả.
• Tất cả hành động trao đổi diễn ra đồng thời trên toàn bộ các vùng đất.
• Quan trọng nhất, mỗi con quỷ chỉ được phép giữ tối đa \(1\) viên ngọc. Nếu tại bất kỳ thời điểm nào một con có nhiều hơn \(1\) viên, nó sẽ phải nộp lại toàn bộ số dư cho Chúa Quỷ để giữ cho cán cân sức mạnh không bị phá vỡ.

Quá trình trao đổi được coi là ổn định ở một năm nào đó nếu số lượng ngọc của mỗi con quỷ trong năm này (trước khi trao đổi) giống hệt với số lượng của nó ở năm trước (trước khi trao đổi). Lưu ý rằng năm \(1\) không bao giờ được coi là ổn định vì đây là năm khởi đầu.

Yêu cầu: Xác định năm đầu tiên mà quá trình trao đổi này trở nên ổn định.

Đầu vào

Dòng đầu tiên chứa số nguyên \(T\) là số lượng bộ test. \((1 \le T \le 10^4)\)

Dòng đầu tiên của mỗi bộ test chứa số nguyên \(n\) là số lượng con quỷ. \((2 \le n \le 2*10^5)\)

Dòng tiếp theo chứa \(n\) số nguyên \(r_1, r_2, ..., r_n\) biểu diễn mỗi con quỷ được chỉ định để nhận ngọc. \((1 \le r_i \le n, r_i ≠ i)\)

Đảm bảo rằng tổng giá trị \(n\) ở tất cả testcase không vượt quá \(2*10^5\).

Đầu ra

Mỗi testcase in ra trên một dòng chứa số nguyên duy nhất là năm đầu tiên mà quá trình trao đổi được coi là ổn định.

Giới hạn

\(40\%\) số test: \(t \le 10, n \le 1000\), tổng \(n\) ở tất cả các test không vượt quá \(2000\).

\(60\%\) số test: Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

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

Đâu ra

2
2
5

Giải thích

Ở testcase thứ \(2\):

• Năm thứ 1, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 1, 1, 1]\). Sau đó quá trình trao đổi năm thứ 1 diễn ra.
• Năm thứ 2, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 1, 1, 1]\). Vì số lượng này giống với năm trước nên quá trình trao đổi được coi là ổn định ở năm này.

Ở testcase thứ \(3\):

• Năm thứ 1, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 1, 1, 1]\). Sau đó quá trình trao đổi năm thứ 1 diễn ra.
• Năm thứ 2, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 1, 1, 0]\). Sau đó quá trình trao đổi năm thứ 2 diễn ra.
• Năm thứ 3, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 0, 1, 0]\). Sau đó quá trình trao đổi năm thứ 3 diễn ra.
• Năm thứ 4, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 0, 0, 0]\). Sau đó quá trình trao đổi năm thứ 4 diễn ra.
• Năm thứ 5, số viên ngọc trước khi trao đổi của các con quỷ lần lượt là \([1, 1, 0, 0, 0]\). Vì số lượng này giống với năm trước nên quá trình trao đổi được coi là ổn định ở năm này.