Realitatea TV



Se consideră un număr natural n și trebuie formate cât mai multe perechi, din care trebuie să facă parte numere cuprinse între 1 și 2n astfel încât suma pătratelor celor două numere din oricare dintre perechi să fie număr prim. Fiecare număr poate face parte din cel mult o pereche.

Fișierul de intrare PAIRS.IN conține o singură linie pe care se află valoarea n.

Prima linie a fișierului de ieșire PAIRS.OUT va conține numărul k al perechilor formate. Fiecare dintre următoarele k linii va conține câte două numere cuprinse între 1 și 2n astfel încăt suma pătratelor celor două numere este număr prim. Perechile pot fi scrise în orice ordine.

1 <= n <= 2500.

PAIRS.IN
7

PAIRS.OUT
7
1 4
2 3
5 6
7 8
9 10
11 14
12 13

Dacă pentru un test se pot obține cel mult X puncte, punctajul acordat va fi X / 2n-k, unde n este numărul din fișierul de intrare, iar k este numărul perechilor formate. Valoarea va fi rotunjită la două zecimale exacte. Dacă nu se obține nici o pereche sau există erori în fițierul de iețire nu se va scorda nici un punct.