Smallest Divisible Partner

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

For each i=1..n, find the minimum j in [1,n] such that n divides i*j. Print i and j per line. A solution always exists (j=n). Breaking the inner search must not end the outer iteration.

Input

One integer 1<=n<=100.

Output

Exactly n lines of i and the minimum valid j.

Subtasks

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

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

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

Examples

Example 1

Input:

6

Output:

1 6
2 3
3 2
4 3
5 6
6 1

Explanation:

For each i, the smallest valid j is printed; j=n always works. Result: 1 6 2 3 3 2 4 3 5 6 6 1.

Example 2

Input:

1

Output:

1 1

Explanation:

For each i, the smallest valid j is printed; j=n always works. Result: 1 1.