Trong giờ giải lao, do lớp vừa học xong các kiến thức về số nguyên tố, nên lớp trưởng của John đã suy nghĩ ra một trò chơi về dãy số cũng khá thú vị. Trò chơi như sau:

Cho một dãy số a[1], a[2], ..., a[n], gồm các số nguyên phân biệt từ 1 đến n. Nhiệm vụ là ta phải sắp xếp các số theo thứ tự tăng dần theo qui tắc sau (có thể áp dụng nhiều lần):

1. Chọn trong dãy số 2 chỉ số i, j (1 ≤ i < j ≤ n; (j - i + 1) là số nguyên tố)

2. Hoán đổi 2 số tại vị trí i, j.

Không cần thiết phải sử dụng số lần nhỏ nhất các qui tắc trên, nhưng không được sử dụng vượt quá 5*n lần.

Input:

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ ~10^5~)
• Dòng tiếp theo chứa n số nguyên phân biệt a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

Output:

• Dòng đầu tiên, in số nguyên k (0 ≤ k ≤ 5n) là số lần qui tắc được sử dụng.
• Dòng tiếp theo in k cặp (i,j) đã hoán đổi. Với i,j thỏa yêu cầu đề bài. Nếu có nhiều đáp án ta in một đáp án bất kỳ.

Ví dụ:

INPUT 1

3
3 2 1

OUTPUT 1

1
1 3

INPUT 2

4
4 2 3 1

OUTPUT 2

3
2 4
1 2
2 4