All Submissions


The people of Cyber City have varying levels of intelligence. The IQ level of the people varies from 1 to 500.The Government of Cyber City is planning to further increase the IQ level of its residents. So the government has roped in two of its best professors, Mr. Wayne and Mr. Fox (both have IQ levels of 999) for training people. So the people have to be divided into two groups. The intelligence level of a group is calculated as the sum of the IQ levels of the people in the group. As professors always want students with higher levels of IQ, so the groups have to be divided such that the intelligence level of the two groups is almost same.

So given the number of people (P) and their IQ levels (iq1, iq2, .., iqp ) your task is to calculate the minimum possible positive difference(may be zero) between the intelligence levels of the two groups when the groups are divided such that the intelligence level of both the groups is almost same. Also calculate the number of ways of dividing the P people in such a way.

Input
  • The first line of the input gives the number of test cases, T. T test cases follow.
  • Each test case is described using two lines.
  • The first line of each test case contains a positive integer P, denoting the number of people.
  • The second line of each test case contains P (iq1, iq2, .., iqp ) space separated positive integers, denoting the IQ levels of P people.

Output

For each test case, output one line containing "Case #t: D W" (quotes for clarity), where t is the case number (starting from 1) and D is the minimum positive difference and W is the number of ways of dividing people modulo 7777777 .D and W are separated with a single space between them.

Constraints

2<= P <= 100
1<= iq1, iq2, .., iqp <= 500

The input file can contain up to 20 cases.

Sample Input


1
3
1 2 4


Sample Output


Case #1: 1 2


Explanation

The minimum possible difference is 1 and the groups can be divided into 2 ways:
  1. Wayne's Group :{ 1, 2}
    Fox's Group: {4}
  2. Wayne's Group :{4}
    Fox's Group: {1, 2}


Problem Setter: Kumar Abhishek



Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0