Coprime Pairs

Given a positive integer n, your task is to find all pairs of integers \( (i, j) \) such that \(1 \leq i < j \leq n\) and their greatest common divisor is 1. In other words, the pair \( (i, j) \) is coprime if \( \gcd(i,j)=1 \).

Print each pair in increasing order, with each pair on its own line and the two numbers separated by a single space. If no valid pairs exist, output nothing.

Note: Use the LaTeX format for mathematical expressions (as seen above) when referring to formulae.

inputFormat

Input is read from standard input. The input consists of a single integer (n) ((1 \leq n \leq 10^4)).

outputFormat

Output each coprime pair ( (i, j) ) on a separate line in the format: 'i j'. The pairs must be listed in increasing order. If there are no valid pairs, print nothing.## sample

1