Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Мала Каћолина је одавно свима нама позната као одличан математичар. Како је лако успела да помножи све могуће парове бројева мањих од милијарду, решила је да себи мало отежа игру са бројевима.

Дефинисаћемо тривијалност броја \(x\) као количник збира његових позитивних делилаца и њега самог (на пример тривијалност броја \(6\) износи \(\frac{1 + 2 + 3 + 6}{6} = 2\)).

За број \(x\) кажемо да је најтривијалнији број у интервалу \([l,r]\) (скупу бројева \(\{ l, l+1, \ldots, r-1, r \}\)), ако припада датом интервалу и његова тривијалност је најмања од тривијалности свих бројева на том интервалу и не постоји ниједан други број мањи од њега који припада интервалу и има исту тривијалност.

Каћолина је себи задала \(Т\) питања облика :

Да ли можете одговорити на ове упите брже од Каћолине (њој отприлике треба две секунде да одговори на сва питања)?

Опис улаза

Прва линија стандардног улаза садржи један природан број \(Т\), који представља број питања које је Каћолина задала. Свака од наредних \(Т\) линија садржи један број, тачније \(i\)-та линија садржи број \(A_i\).

Опис излаза

За сваки од задатих \(Т\) упита исписати најтривијалнији број у задатом интервалу, тачније у \(i\)-тој линији исписати најтривијални број у интервалу [\(2\), \(A_i\)].

Пример

Улаз

1
4

Излаз

3

Објашњење примера

Дат је само један упит и потребно је наћи најтривијалнији број у интервалу \([2, 4]\).

Тривијалност броја 2 : \(\frac{1 + 2}{2} = 1.50\)

Тривијалност броја 3 : \(\frac{1 + 3}{3} = 1.33\)

Тривијалност броја 4 : \(\frac{1+2+4}{4} = 1.75\)

Најмању тривијалност има број \(3\), тако да је он решење овог примера.

Ограничења

Подзадаци