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 {W₁, W₂, ..., W_n}, where W_i denotes the weight of the i^th stone. You can remove some stones leaving 2m (m > 0) stones as W_p1, W_p2, ..., W_p2m such that

W_p1 + W_p2m > W_p2 + W_p2m-1 > W_p3 + W_p2m-2 > ... > W_pm + W_pm+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 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 10⁹.

For each case, print the case number and the number of possible orderings modulo 2³².

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}.