First Missing Positive

You are given an unsorted array of n integers. The task is to find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.

In other words, given an array nums, find the minimal positive integer that is not present in the array. Note that the answer is always in the range \(\{1,2,\ldots,n+1\}\). For example:

• If nums = [1, 2, 0], the answer is 3.
• If nums = [3, 4, -1, 1], the answer is 2.
• If nums = [7, 8, 9, 11, 12], the answer is 1.

inputFormat

The input is read from stdin and contains multiple test cases. The first line contains a single integer T representing the number of test cases. Each test case starts with an integer n on a new line denoting the size of the array, followed by a line containing n space-separated integers.

Example:

3
3
1 2 0
4
3 4 -1 1
5
7 8 9 11 12

outputFormat

For each test case, output a single line containing the smallest missing positive integer. The output is written to stdout.

Example output for the above input:

3
2
1

## sample

1
3
1 2 0

3