Taco Search: Comparing Brute Force and Binary Search

This problem requires you to implement two search algorithms on a sorted array: a brute force search and a binary search. For each test case, you are given a sorted array of integers and a key to search for. Your program should perform both searches, count the number of comparisons made by each method, and output the results.

If the key is found, output its 0-indexed position along with the number of comparisons made by the brute force search and binary search respectively. If the key is not present, output -1 for the index. Note that the number of comparisons should include every comparison made during the search.

The binary search should follow the standard algorithm. When the array is empty, both the brute force and binary search should return an index of -1 with 0 comparisons.

Formula: For binary search, the mid index is computed as \( mid = \lfloor (low + high) / 2 \rfloor \).

inputFormat

The input is read from standard input (stdin). It starts with an integer T representing the number of test cases. Each test case consists of three parts:

1. A line containing an integer n, the number of elements in the array.
2. A line with n space-separated integers in sorted order.
3. A line containing the integer key to search for.

Note: When n is 0, the array is empty.

outputFormat

For each test case, output a single line containing three space-separated integers:

• The index of the key found by brute force search (or -1 if not found).
• The number of comparisons made by the brute force search.
• The number of comparisons made by the binary search.

The output should be printed to standard output (stdout).

## sample

5
10
1 2 3 4 5 6 7 8 9 10
6
10
1 2 3 4 5 6 7 8 9 10
11
0

1
5
5
1
5
1

5 6 3
-1 10 4
-1 0 0
0 1 1
-1 1 1

</p>