Problem Statement

Cubicle Preferences A company has 2n employees with ID numbers 1, 2, ..., 2n . They must be divided into n cubicles, with exactly two employees in each cubicle. Every cubicle has a window seat and an aisle seat . After the cubicles are formed, you choose an integer x . In exactly x cubicles the employee with the smaller ID occupies the window seat. In the remaining n - x cubicles the employee with the larger ID occupies the window seat. You are given the IDs of the employees sitting in the window seats. They are b1, b2, ..., bn , where b1 < b2 < ... < bn . Find the number of different values of x ( 0 <= x <= n ) for which it is possible to pair the employees into cubicles so that the employees occupying the window seats are exactly b1, b2, ..., bn . Input The first line contains a single integer t ( 1 <= t <= 100 ) - the number of test cases. The first line of each test case contains a single integer n ( 1 <= n <= 5000 ). The second line of each test case con