Komični Kvadrat
시간 제한1초메모리 제한1024 MB
각 구간 [a, b]마다 그 구간의 공집합이 아닌 부분집합의 곱이 어떤 수의 제곱이 되는 경우를 찾고, 그 제곱근 중 가장 작은 값을 구하거나 불가능하면 nema를 출력한다.
문제
Mladi Patrick je završio svoju (srednjoškolsku) natjecateljsku karijeru i sišao s uma. Umjesto da i dalje rješava informatičke zadatke, odlučio je svoje vrijeme tratiti na proučavanje brojeva.
Da stvar postaje ozbiljna potvrdili su i njegovi roditelji, koji su ga pod okriljem noći zatekli za radnim stolom kako umire od smijeha.
“Nijedan od brojeva 6, 10 i 15 nije potpuni kvadrat, ali je zato njihov umnožak 6 · 10 · 15 = 900 potpuni kvadrat, hahahaha, urnebes!”
Naravno, roditelji su ga odmah odveli na pregled, ali ispada da se medicinska znanost još nije susrela s ovakvim simptomima.
Patrick je na sve to samo veselo odgovorio: “Riješite sljedeći zadatak i postat će vam jasno da je samnom sve u redu.”
Nazovimo skup X = {x1, x2, . . . , xn} komičnim ako je umnožak njegovih elemenata x1 · x2 · . . . · xn potpuni kvadrat. Za zadani interval brojeva, pronađite najmanji broj čiji je kvadrat jednak umnošku nekog komičnog podskupa brojeva iz zadanog intervala, ili odredite da niti jedan podskup brojeva danog intervala nije komičan.
Možete li se uvjeriti da Patrick nije lud?
입력
U prvom se retku nalazi prirodan broj t (1 ≤ t ≤ 150) koji označava broj testnih primjera koje je potrebno riješiti.
U i-tom od sljedećih t redaka nalaze se brojevi ai i bi (1 < ai < bi ≤ 4900) koji redom označavaju donju i gornju (uključivu) granicu intervala iz teksta zadatka za i-ti test primjer.
출력
Za svaki testni primjer potrebno je ispisati najmanji broj k takav da je k2 jednak umnošku elemenata nekog nepraznog komičnog podskupa skupa {x ∈ N | a ≤ x ≤ b}.
Ako takav broj ne postoji, ispišite riječ “nema”.
Broj k će biti manji od 263.