Server Time: Wed Sep 30, 2020 10:09 pm
Welcome ( logout
C - Aladdin and the Black Stones
  PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 32 MB

It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the third mystery.

In the cave, Aladdin found some black stones arranged in a line. The weights of the stones were not necessarily equal. Though the stones looked gentle, he soon found that he cannot even walk over the stones. Some strange magic were stopping him passing the stones. So, he planned to move the stones. But when he took the first stone, he heard a sound. And it said,

"Remove some stones leaving even number of stones, the outer pair should be the heaviest. If the pair is removed, the new outer pair should be the heaviest and if this pair is removed the new outer pair is the heaviest and so on. How many ways you can do? Find it and I will let you through."

Aladdin solved this task and moved forward. Now your task is to do the same, you are given n stones W1, W2, ..., Wn, where Wi denotes the weight of the ith stone. You can remove some stones leaving 2m (m > 0) stones as Wp1, Wp2, ..., Wp2m such that

Wp1 + Wp2m > Wp2 + Wp2m-1 > Wp3 + Wp2m-2 > ... > Wpm + Wpm+1

Remember that you cannot change the order of the stones. Now your task is to find the number of ways you can do it. Two orderings are different if m is different or there is at least a position i, where the stones are different.

Input

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

Each case starts with a line containing an integer n (2 ≤ n ≤ 500) and n integers denoting the weight of the stones. Weights can be any integer between 1 and 109.

Output

For each case, print the case number and the number of possible orderings modulo 232.

Sample Input

Output for Sample Input

4

3 1 1 1

4 1 4 7 20

4 10 18 2 9

7 2 4 1 4 5 9 13

Case 1: 3

Case 2: 7

Case 3: 6

Case 4: 61

Note

1.      For the first case, the valid orderings are {1(first stone), 1(second stone)}, {1(first stone), 1(third stone)} and {1(second stone), 1(third stone)}.

2.      For the second case, the valid orderings are, {1, 4}, {1, 7}, {1, 20}, {4, 7}, {4, 20}, {7, 20}, {1, 4, 7, 20}.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan