KPEQU - Equation

no tags 

You are given integer positive number N. Find the number of solutions in positive integer numbers of the following equation:

1/N! = 1/X + 1/Y

Input

Each line of input file contains one integer number N (1 ≤ N ≤ 104). The last line contains 0 and shouldn't be processed. Number of lines in the input does not exceed 30.

Output

For every line in the input write the answer on a separate line.

Example

Input:
1
2
0

Output:
1
3

hide comments
Sandytea: 2010-06-29 12:31:39

Change N! into prime factors and find the law.

Nikhil Garg: 2009-12-26 23:02:26

If i am right , answer for n=5 is 63 , aint it ?


Added by:Pavel Kuznetsov
Date:2007-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Vologda 2007