Find Pair with Given Sum

You are given an array of integers and a target sum \(S\). Your task is to find a pair of indices \((i, j)\) such that the sum of the elements at these indices equals \(S\). If such a pair exists, output the pair of indices (with the first occurring index being reported first). Otherwise, output "None".

Note: Each input array will have at most one valid pair to output, and the same element from the array cannot be used twice unless it appears twice.

For example, given the array [2, 7, 11, 15] with target sum 9, the correct output is "0 1" because \(2 + 7 = 9\). If there is no such pair, output "None".

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) denoting the number of test cases. Each test case consists of the following:

• The first line contains an integer \(N\), the number of elements in the array.
• The second line contains \(N\) space-separated integers, representing the elements of the array.
• The third line contains an integer representing the target sum \(S\).

It is guaranteed that \(N \geq 1\).

outputFormat

For each test case, output a single line to standard output (stdout). If a valid pair is found, print the two indices separated by a space. If no valid pair exists, output "None".

## sample

4
4
2 7 11 15
9
5
1 2 3 4 5
10
4
0 0 0 0
0
5
1000000 2999 7000 5000 4000000
1007000

0 1
None
0 1
0 2

</p>