Find the Smallest Missing Positive Integer

Given an array of integers, your task is to find the smallest missing positive integer that does not appear in the array. This problem requires efficient checking, as the code should determine, for a given array (A) of size (n), the smallest integer in the natural number sequence (1, 2, 3, \ldots) that is absent from (A).

Use an algorithm with near linear time complexity if possible.

inputFormat

The input begins with an integer (T) denoting the number of test cases. Each test case consists of two lines. The first line contains an integer (n), the size of the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line with the smallest missing positive integer.## sample

1
6
3 4 -1 1 9 5

2