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
rk: 2015-05-06 10:50:30

sry even ouput given by users plz help.

Last edit: 2015-05-06 11:17:17
THE_SCORPION: 2013-08-29 15:42:36

I don't understand what's the benefit of the Y & X

Ouditchya Sinha: 2013-04-25 10:59:49

My AC solution for N = 10^4 begins with 221454 & ends with 984375 and is 1019 characters long. :)

Srijan Khare: 2012-12-29 18:04:36

my AC solution gives beginning with 3273...and ending with...4375 for N=50000

Osschef Wum Enear: 2012-04-06 11:20:23

So the answer for N=50000 has 6966 digits, beginning with 3467... and ending in 1129 zeros.
Computed in 0.4 secs :D

Lureohc Otnafifa: 2011-04-24 03:51:02

is there any modulus for the answer..?
what is the answer for N = 10^4 ?

Anuj Mahajan: 2011-03-07 22:08:48

plz.....some test cases

say for n = 5 and 6

Egor: 2011-02-20 15:31:41

How to optimize solution?

Last edit: 2011-02-20 16:13:53
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:0.236s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Vologda 2007