Odd Man Out

Interview

Time limit5sMemory limit512 MB

Summary

Given an odd-length list where every number appears twice except one, find the number that appears once.

Level: Medium4 of 10
Topics: Bit manipulation, Hash map
Solved: No attempts yet

Problem

You are hosting a party for $G$ guests. You sent invitations to couples only, and each couple got its own invitation number $C$ , the same number for both partners. A couple adds two guests carrying the same number, so the guest count should be even. It is not: the number of guests $G$ who showed up is odd, so exactly one guest came alone.

You ask every guest for an invitation number and write the answers down. Find the invitation number of the guest who came alone.

Input

The first line contains the number of test cases $N$ .

Each test case is given on two lines.

The first line contains the number of guests $G$ .
The second line contains $G$ space separated integers, the invitation number $C$ of each guest.

Limits

$1 \le N \le 50$
$3 \le G < 100$ , and $G$ is odd.
$0 < C \le 2147483647$
In each test case exactly one number appears once and every other number appears exactly twice.

Output

For each test case print one line containing Case #x: followed by the invitation number $C$ of the guest who came alone. Here $x$ is the test case number, counting from 1.

Examples4

Example 1

Input

3
3
1 2147483647 2147483647
5
3 4 7 4 3
5
2 10 2 10 5

Expected output

Case #1: 1
Case #2: 7
Case #3: 5

Example 2
Input
```
1
3
1 2 2
```
Expected output
```
Case #1: 1
```

Example 3

Input

1
3
2147483646 2147483647 2147483646

Expected output

Case #1: 2147483647

Example 4

Input

2
5
9 1 2 1 2
7
4 5 6 5 6 4 7

Expected output

Case #1: 9
Case #2: 7