Cặp số \((a,n)\) được gọi là "đẹp đôi" nếu chúng thỏa mãn những điều kiện sau:

• \(a,n\in \mathbb{N}\) và \(a\ge 2,n\ge 2\)

• Tồn tại một dãy số \(\left\{u\right\}\) thỏa mãn:

• \(u_1=p+1;u_i=u_{i-1}+1\) với \(1\le i\le n-1\) và \(p\in \mathbb{P}\)

• \(u_i\notin \mathbb{P}\) với \(1\le i\le n-1\)

• \(u_{n-1}+1 \in \mathbb{P}\)

• Tồn tại chỉ số \(j(1\le j\le n-1)\) thỏa mãn: \(u_j=a\)

(trong đó: \(\mathbb{P}\) là tập hợp các số nguyên tố)

Hay nói cách khác tồn tại dãy \(u\) gồm các số tự nhiên liên tiếp bắt đầu từ \(p + 1\) và kết thúc tại \(p+n-1\) (với \(p\) và \(p+n\) là các số nguyên tố) thỏa mãn \(u\) chỉ chứa hợp số và \(u\) chứa số \(a\)

Yêu cầu: Cho số nguyên dương \(a(a\ge 2)\). Tìm số nguyên dương \(n(n\ge 2)\) thỏa mãn \((a,n)\) là cặp "đẹp đôi". Nếu không tồn tại \(n\) thỏa mãn thì in ra \(0\)

Input

• Input gồm nhiều truy vấn, mỗi truy vấn là một dòng chứa một số nguyên dương \(a(a\ge 2)\)

• Input kết thúc bởi số 0.

Output

• Ứng với mỗi dòng chứa số nguyên dương \(a\), in ra đáp án tương ứng

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(2\le a\le 10\)

• Subtask \(2\) (\(80\%\) số điểm): \(2\le a\le 10^6\)

Example

2
4
0 

0
2

int a;
while(cin >> a) {
    if (a == 0) break;
    // ...
}