SQUA_REV - Revenge of the squares

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^20.

Output

Print the illustrated above number R for each test.

Example

Input:
5
7
78185824586267361855 Output: 1
0
3

Added by:HWK
Date:2011-02-25
Time limit:1.096s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-03-02 16:13:14 HWK
This should be a shortening problem.
Because of a mistake on my part it wasn't. So I made the new problem SQUAREV with ID 8431. Please submit all new solutions there.
If the previous solvers numerix, Erick Wong, sevenkplus and abhijith reddy d will agree I'll hide this problem. Please leave a comment.
Thank you and sorry for the inconvenience caused.

Last edit: 2011-03-01 15:12:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.