"And when you think that they actually made the tests for joingraf..."

## Task

After conducting the tests for the joingraph problem at the last RoAlgo contest, the committee realized that a special problem was still needed. After extensive discussions, the following problem was created:

Given $t$ arrays $a$ of $n$ numbers, find the length of the longest subarray that contains at most $3$ distinct numbers. An example of such a subarray is: $9 \ 1 \ 0$.

## Input data

The first line of the input contains the number $t$. For each test, the first line contains $n$, representing the number of numbers. The second line contains the $n$ numbers.

## Output data

For each test, print the maximum length of a subarray with at most $3$ distinct numbers.

## Constraints and clarifications

- $1 \leq t \leq 1\ 000$
- $1 \leq n \leq 10^6$
- The sum of the lengths of all $t$ arrays does not exceed $10^6$.
- $1 \leq a_i \leq 10^9$

# | Points | Constraints |
---|---|---|

1 | 0 | Example |

2 | 14 | $1 \leq n \leq 100$ |

3 | 22 | $1 \leq n \leq 5\ 000$ |

4 | 38 | $1 \leq n \leq 100\ 000$ |

5 | 26 | No additional constraints |

## Example

`stdin`

```
5
10
1 4 7 4 2 4 7 3 2 3
8
1 2 4 1 5 3 1 2
10
6 8 9 1 8 5 4 6 3 2
6
1 1 1 2 2 2
12
1 5 8 3 2 5 7 4 9 5 7 4
```

`stdout`

```
6
4
4
6
3
```

### Explanation

The subarray `4 7 4 2 4 7`

contains $3$ distinct numbers. There is no subarray with more than $6$ numbers that meets the criteria.