Given a sequence of digits, there may be many ways to add “+” and “-” between them to form an expression whose evaluated result is 0. For example, there are 3 solutions to the sequence “1 2 1 2”, which are “1 + 2 - 1 - 2”, “1 - 2 - 1 + 2” and “12 - 12”. Note that the sign must be put between two digits (which means “- 1 + 2 + 1 - 2” is not a valid solution), but it is not necessary to add signs between every pairs of digits (“12 - 12” is valid, for instance). Moreover, the order of digits in the sequence may not be changed. Find the number of valid solutions to a given sequence.
Each test case consists of two lines. The first line is an integer N (2 ≤ N ≤ 12) denoting the number of digits in the sequence, and the second line contains N digits in the range [1, 9]. The input is terminated by a zero after the last test case, and the number of test cases will be no more than 1500.
For each case, output “Case i:” and then the number of solutions, seperated by a space character, i is the number of test case starting from 1.