Store Credit

Interview

Time limit5sMemory limit512 MB

Summary

Given a credit C and a list of item prices, find the two positions whose prices sum exactly to C and print them in increasing order.

Level: Easy3 of 10
Topics: Array, Hash map, Two pointers, Brute force
Solved: No attempts yet

Problem

You receive a store credit of $C$ at a local store and want to spend it on exactly two items. You first walk through the store and write down every item on sale, which gives you a list $L$ . From that list you buy two items whose prices add up to the credit exactly.

The answer is the pair of integers giving the positions of those two items in the list, smaller number first. Positions are counted from 1.

Input

The first line contains the number of test cases $N$ . The $N$ test cases follow, each on three lines.

The first line contains the credit $C$ you have at the store.
The second line contains the number of items $I$ in the store.
The third line contains $I$ integers separated by single spaces. Each integer $P$ is the price of one item.

Limits

$1 \le N \le 10$
$5 \le C \le 1000$
$3 \le I \le 100$
$1 \le P \le 1000$
Every test case has exactly one pair of items that satisfies the condition.

Output

For each test case, print one line containing Case #x: followed by the positions of the two items whose prices add up to the store credit, smaller position first, separated by a single space. Here $x$ is the test case number starting from 1.

Examples1

Example 1

Input

3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3

Expected output

Case #1: 2 3
Case #2: 1 4
Case #3: 4 5