G. I-5 Drive
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Guillaume is traveling to Los Angeles in a self-driving car, making for a seemingly relaxing trip. Driven half mad by Interstate 5's mind-numbingly boring scenery, he passes the time by pondering math problems.

This time, he wants to determine the number of ordered pairs of prime numbers ($$$p,q$$$) such that when $$$N=p^2+q^3$$$ is written in base $$$T$$$, without leading zeros, each digit from $$$0$$$ to $$$T-1$$$ appears exactly once.

Solve the math problem.

Input

Line 1: One integer, $$$T$$$ ($$$2 ≤ T ≤ 10$$$).

Output

Line 1: One integer, representing the number of ordered pairs of prime numbers ($$$p,q$$$), as described in the problem statement.

Example
Input
3
Output
0
Note

Written in base-$$$3$$$, the only possible $$$N$$$ are $$$012, 021, 102, 120, 201$$$, and $$$210$$$. The maximum is $$$210$$$, which is $$$21$$$ in base $$$10$$$. The smallest possible number that can be written as $$$p^2+q^3$$$ is $$$3^2+2^3=17$$$, and the second smallest is $$$2^2+3^3=31$$$, so none of these possible $$$N$$$ can be written in this form. Thus, the answer is $$$0$$$.