Hai vòng: cặp chia hết (Smallest Divisible Partner)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n$. Với mỗi $i$ từ 1 đến $n$, tìm số nguyên j nhỏ nhất trong $[1,n]$ sao cho tích $i\cdot j$ chia hết cho $n$. In đúng $n$ dòng, dòng i gồm i j. Luôn có đáp án vì $j=n$ thỏa. Cách dùng hai vòng lặp nên break vòng j ngay sau nghiệm đầu; vòng i vẫn tiếp tục.

Input

Một số nguyên $1\le n\le100$.

Output

Đúng $n$ dòng, mỗi dòng gồm i và j nhỏ nhất.

Subtask

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

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

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

Ví dụ

Ví dụ 1

Input:

6

Output:

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

Giải thích:

Với mỗi i, j nhỏ nhất thỏa n chia hết i*j được in; j=n luôn là ứng viên. Kết quả kiểm tra với dữ liệu này: 1 6 2 3 3 2 4 3 5 6 6 1.

Ví dụ 2

Input:

1

Output:

1 1

Giải thích:

Với mỗi i, j nhỏ nhất thỏa n chia hết i*j được in; j=n luôn là ứng viên. Kết quả kiểm tra với dữ liệu này: 1 1.