Longest Repeating Pattern

Given a sequence of integers, find the length of the longest repeating pattern in the sequence. More formally, you need to compute the maximum k (with 0 ≤ k < n) such that the first k elements of the sequence also form a suffix (a "border") of the sequence. If no such pattern exists, output 0.

This problem can be efficiently solved using the prefix function (also known as the failure function) from the Knuth-Morris-Pratt (KMP) algorithm. The prefix function helps in finding the longest proper prefix of a string (or sequence) which is also a suffix of it.

Note: The pattern must be a proper prefix of the entire sequence, meaning it cannot be equal to the entire sequence itself.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains a single integer T, the number of test cases.
• For each test case:
• The first line contains an integer N, the length of the sequence.
• The second line contains N space-separated integers representing the sequence.

outputFormat

For each test case, output a single line to stdout containing the length of the longest repeating pattern. If no such pattern exists, output 0.

## sample

2
10
1 2 3 1 2 3 4 5 1 2
6
1 2 3 4 5 6

3
0

</p>