National Olympiad in Informatics, China, 2001

The inverse tangent function can be expressed as an infinite series, as shown below:

$$\begin{array}{}\text{(1)}& {\displaystyle \begin{array}{r}\arctan (x)=\sum _{n=0}^{\mathrm{\infty }}\frac{(-1{)}^n{x}^{2n+1}}{2n+1}(0\le x\le 1)\end{array}}\end{array}$$

It is commonly known that the inverse tangent function can be used to compute $\pi$. For example, an easy way to compute $\pi$ is using the method:

$$\begin{array}{}\text{(2)}& {\displaystyle \begin{array}{rl}\pi & =4\arctan (1)\\ & =4(1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\dots )\end{array}}\end{array}$$

Of course, this method is rather inefficient. We can apply the tangent angle sum identity:

$$\begin{array}{}\text{(3)}& {\displaystyle \begin{array}{r}\tan (\alpha +\beta )=\frac{\tan (\alpha )+\tan (\beta )}{1-\tan (\alpha )\tan (\beta )}\end{array}}\end{array}$$

After some simple manipulation, the following is obtained:

$$\begin{array}{}\text{(4)}& {\displaystyle \begin{array}{r}\arctan (p)+\arctan (q)=\arctan \left(\frac{p+q}{1-pq}\right)\end{array}}\end{array}$$

Using this identity, let $p={\displaystyle \frac{1}{2}}$ and $q={\displaystyle \frac{1}{3}}$, then ${\displaystyle \frac{p+q}{1-pq}}=1$. Therefore:

$${\displaystyle \arctan \left(\frac{1}{2}\right)+\arctan \left(\frac{1}{3}\right)=\arctan \left(\frac{\frac{1}{2}+\frac{1}{3}}{1-\frac{1}{2}\cdot \frac{1}{3}}\right)=\arctan (1)}$$

Using the inverse tangents of ${\displaystyle \frac{1}{2}}$ and ${\displaystyle \frac{1}{3}}$ to calculate $\arctan (1)$, the speed is drastically improved.

We take equation (4) and write it in the following form:

$${\displaystyle \arctan \left(\frac{1}{a}\right)=\arctan \left(\frac{1}{b}\right)+\arctan \left(\frac{1}{c}\right)}$$

where $a$, $b$, and $c$ are each positive integers.

The problem is, for a given $a$ $(1\le a\le 60000)$, find the value of $b+c$. It is guaranteed that for any $a$ there will always exist an integer solution. If there are multiple solutions, you are required to find the minimum value of $b+c$.

Input Specification

The input consists of a single positive integer $a$, where $1\le a\le 60000$.

Output Specification

The output should contain a single integer, the value of $b+c$.

Sample Input

1

Sample Output

5

Problem translated to English by Alex.