Description

Input a natural number $n$. For a reduced fraction $a/b$ (a fraction whose numerator and denominator are coprime) that satisfies $1 \le b \le n, 0 \le a/b \le 1$, find all fractions meeting the conditions.

Here is an example. When $n=5$, all solutions are:

$$\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34 ,\frac45,\frac11$$

Given a natural number $n$, write a program to output all solutions in increasing order of their values.

Note:

1. The greatest common divisor of $0$ and any natural number is that natural number.
2. “Coprime” means the greatest common divisor of the two natural numbers equals $1$.

Input Format

A single line containing a natural number $n$.

Output Format

Each fraction occupies one line, in increasing order.

5

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 160$.

USACO 2.1

Translation from NOCOW.

Translated by ChatGPT 5