List Divisible Pairs

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$, list every pair $(i,j)$ satisfying $1\le i<j\le n$ and $j\bmod i=0$. Print one pair per line as i j, in ascending order of $i$ and then $j$. If no pair exists, print nothing.

Input

One line contains integer $n$.

Output

Print the pairs in the specified order, or empty output if none.

Subtasks

• Subtask 1 (20%): $1\le n\le 12$.

• Subtask 2 (30%): $1\le n\le 40$.

• Subtask 3 (50%): $1\le n\le 100$.

Examples

Example 1

Input:

4

Output:

1 2
1 3
1 4
2 4

Explanation:

List multiples strictly greater than i, in increasing order; n=1 has empty output.

Example 2

Input:

1

Output:

Explanation:

List multiples strictly greater than i, in increasing order; n=1 has empty output.