Fancy is learning mathematics recently. He's already mastered the use of multiplication and addition days before, so today he's going to learn prime number.

After reading the learning material, he's been asked to complete a simple test. He's been given an integer `X` larger than 1, using multiplication, addition and at most 3 prime numbers, how many ways could he get the answer as `X` exactly?

Since that Fancy is a new learner of mathematics, he's still not familiar with brackets. So in the calculation, the addition is always performed after multiplication.

There will be multiple test cases. Each test case contains a single integer `X` (1 < `X` ≤ 80000) in one line.

提交代码