Some Pakistani Army helicopter wanted to launch a military operation called Operation Searchlight against Bengali civilians. They have n helicopter to lunch this mission. Each helicopter must land after flying a fixed distance. Somehow Mukti Bahini came to know about their plan. Now they want to destroy all of their helicopters. Because of that they want to create a place to destroy helicopters. If any helicopter will land that place the helicopter will destroyed in that moment. As you are a good programmer commander NAJ gives task to choose a place where they can destroyed all helicopter.

INPUT

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 1000) denoting the number Helicopters. The next line contains N integers denoting the flying distance of ith Helicopter. Each helicopter must land after flying exactly a[i] (1 ≤ a[i] ≤1000000) distance.

OUTPUT

For each case, output the case number and the desired value. If there was multiple answer print the smallest one. Since the result can be very large, you have to print the result modulo 1000000007.