Given a number calculate the product N of their digits bigger than zero. The output is the number R of different (!) presentations of N in the form A×A+B×B with A and B being positive integers including zero.

Input

Twenty tests with one positive integer < 10²⁰.

Output

Print the illustrated above number R for each test.

Example

Input:
5
7
78185824586267361855
Output:
1
0
3