Description

he following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.

  * * *

x

  * * *
* * *
-------
* * * *

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed. Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

Input

There are more than one case.Each case contains: Line 1: N, the number of digits that will be used .N=0 means the end of input. Line 2: N space separated digits with which to solve the cryptarithm

Output

A single line with the total number of unique solutions. Here is the solution for the sample input:

  2 2 2
x   2 2
 ------
  4 4 4
4 4 4

4 8 8 4

Sample

Input

5
2 3 4 6 8

Output

1