The Celebrity Problem

Imagine there are 'N' people at a party, each assigned a unique ID from 0 to N-1. A celebrity at the party is a person who is known by everyone but knows no one else.

Problem Statement:

You are given a helper function knows(A, B) that returns "true" if person with ID 'A' knows person 'B' and "false" otherwise. The task is to identify the celebrity at the party. If no celebrity exists, return -1.

Input:

The first line contains an integer 'T' representing the number of test cases. For each test case, the first line contains an integer 'N', which is the number of people at the party.

Output:

For each test case, output a single integer: the ID of the celebrity, or -1 if there is none.

Example:

Note:

- The knows function is pre-defined and should not be implemented by you.

Constraints:

• 1 <= T <= 50
• 2 <= N <= 10⁴
• There is at most one celebrity at the party.
• There are at least 2 people at the party.

Additional Note:

- Minimize calls to the 'knows' function during implementation.