Fractions

Time limit2sMemory limit512 MB

Summary

Given n, represent 1 - 1/n as a sum of fractions with denominators dividing n and strictly between 1 and n, or report that no such sum exists.

Level: Hard8 of 10
Topics: Math, Number theory, Greedy, Implementation
Solved: No attempts yet

Problem

You are given a positive integer $n$ .

Find a sequence of fractions $a_i, b_i$ ( $i = 1 \dots k$ , where $a_i$ and $b_i$ are positive integers) for some $k$ such that

[\begin{cases} b_i \text{ divides } n, 1 < b_i < n \text{ for } i = 1 \dots k \ 1 \le a_i < b_i, \text{ for } i = 1 \dots k \ \sum_{i=1}^{k}{\frac{a_i}{b_i}} = 1 - \frac{1}{n} \end{cases}]

Input

The input consists of a single integer $n$ ( $2 \le n \le 10^9$ ).

Output

On the first line print "YES" if such a sequence of fractions exists, or "NO" otherwise.

If such a sequence exists, the following lines describe the sequence in this format.

The second line contains the integer $k$ ( $1 \le k \le 100\,000$ ), the number of elements in the sequence. If such a sequence exists, a sequence of length at most $100\,000$ is guaranteed to exist. The next $k$ lines contain the fractions of the sequence, with two integers $a_i$ and $b_i$ on each line.

Hint

The second example has the sequence $\frac{1}{2}$ , $\frac{1}{3}$ , and $\frac{1}{2}+\frac{1}{3} = 1 - \frac{1}{6}$ .

Examples2

Example 1
Input
```
2
```
Expected output
```
NO
```
Example 2
Input
```
6
```
Expected output
```
YES
2
1 2
1 3
```