numere

Pentru un număr natural nenul $X$, se numește divizor propriu al lui $X$, un divizor natural al lui $X$, diferit de $1$ și $X$. De exemplu, pentru numărul $20$ divizorii proprii sunt $2, 4, 5, 10$, iar numărul $20$ are $4$ divizori proprii.

Cerință

Să se scrie un program care să rezolve următoarele probleme:

1. Se dă un număr natural $N$. Determinați cel mai mic număr din intervalul închis $[1,N]$ care are număr maxim de divizori proprii.
2. Se dau trei numere $N$, $M$ și $T$. Determinați câte intervale de forma $[a,b]$ au proprietatea că există exact $M$ numere naturale care au $T$ divizori proprii.

Date de intrare

Fișierul de intrare numere.in conține pe prima linie un număr natural $P$ reprezentând cerința din problemă care trebuie rezolvată.

Dacă $P = 1$ atunci pe a doua linie se găsește un număr natural $N$, reprezentând extremitatea din dreapta a intervalului.

Dacă $P = 2$ atunci pe a doua linie se găsesc trei numere: un număr natural $N$, un număr natural $M$ și un număr natural $T$ cu semnificațiile din enunț.

Date de ieșire

Dacă $P = 1$ atunci fișierul de ieșire numere.out conține pe o singură linie numărul cel mai mic determinat care are număr maxim de divizori.

Dacă $P = 2$ atunci fișierul de ieșire numere.out conține pe o singură linie numărul de intervale determinate care au proprietatea cerută

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 100 \ 000$
• $1 \leq T \leq 100 \ 000$
• $1 \leq a \leq b \leq N$
• Pentru rezolvarea corectă a cerinței $1$ se acordă $40$ de puncte, pentru rezolvarea corectă a cerinței $2$ se acordă $60$ de puncte.

Exemplul 1

numere.in

1 
20

numere.out

12

Explicație

$12$ are $4$ divizori proprii și este cel mai mic număr cu $4$ divizori proprii din $[1,20]$.

Exemplul 2

numere.in

2
10 3 2

numere.out

6

Explicație

$[1,10]$, $[2,10]$, $[3,10]$, $[4,10]$, $[5,10]$, $[6,10]$ sunt cele $6$ intervale în care se găsesc exact $3$ numere cu $2$ divizori proprii ($6$, $8$, $10$ sunt numerele cu $3$ divizori proprii).