Minimum Jumps Problem Statement

In the city of Berland, Bob and his wife visit the ‘Arcade’ mall every Friday. The mall has shops arranged in a line, and Bob can jump between these shops using trampolines. From any shop i, he can jump to any shop between i and i + Arr[i], where Arr[i] is a given constant for each shop.

Bob's wife starts her journey at shop 0 and ends at shop N-1. Determine the minimum number of trampoline jumps Bob needs to make to reach from shop 0 to shop N-1. If it's not possible, return -1.

Input:

The first line of input contains a single integer T, representing the number of test cases.
Each test case includes:
A positive integer N, the number of shops.
N space-separated integers representing the array Arr.

Output:

For each test case, output the minimum number of jumps required, or -1 if unreachable.

Example:

Input:

2
5
2 3 1 1 4
3
3 2 1

Output:

2
-1

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 10⁴
• 0 ≤ Arr[i] <= N

Note:

Implementation of the function is required. Printing is handled externally.