3606 -- Sheryl's Circuit II

Language:

Sheryl's Circuit II

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 529		Accepted: 222

Description

After graduating from college, Sheryl intents to use her circuit to make money. (If you are not familiar with Sheryl’s circuit, turn to Problem 3605 for reference.) She attempts to develop her circuit into a periodic clock generator. The first thing Sheryl wants to know is how many rising edges and falling edges exist in the signal produced when the INPUT goes continuously from all 0s to all 1s. ((0, 0, 0... 0, 0) -> (0, 0, 0... 0, 1) -> (0, 0, 0... 1, 0) -> (0, 0, 0... 1, 1) -> ... -> (1, 1, 1... 1, 0) -> (1, 1, 1... 1, 1))

Figure 1

Consider the circuit showed in Figure 1, when the INPUT goes continuously from (0, 0, 0, 0) to (1, 1, 1, 1), the signal produced by the circuit is the sequence (0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1) which consists of 3 rising edges and 2 falling edges respectively.

Given Sheryl's circuit, your task is to calculate the number of rising edges and the number of falling edges. Since the answers might be very large, you are only required to output the numbers modulo 9973.

Input

There are multiple test cases.
The first line contains the number of test cases.
Each test case begins with an integer N( ≤ 10000), the number of inputs of Sheryl's circuit. It is guaranteed that N equals 2^k, where k is an integer.
Next N - 1 numbers describe the types of the BAUs, 0 for ∨ and 1 for ∧. The describing order is from top level to bottom level. For the same level it is from left to right.

Output

For each test case output the number of rising edges and the number of falling edges modulo 9973 in a separate line.

Sample Input

1
4
1 0 1

Sample Output

3 2

Source

POJ Founder Monthly Contest – 2008.06.29, Dagger