Ержүрек қаһарман қауіпті үңгірге аттанады. Бастапқыда оның \(h\) денсаулық ұпайы бар.

Зынданда қаһарман құбыжықтарға кезектесіп шайқасады. Раундтар 1-ден басталады.

Раунд номері \(i\) кезінде:

• Егер қаһарманның қазіргі денсаулығы \(i\)-ге бөлінсе, құбыжық критикалық соққы жасайды: денсаулық \(h :=\) \(\frac{h}{i}\)

• Әйтпесе, қаһарман жеңіл жарақат алады: денсаулық 1-ге азаяды, яғни \(h := h - 1\)

Шайқастар қаһарманның денсаулығы 0-ге тең болғанша жалғасады. Осы сәтте қаһарман өледі.

Қаһарманның қай раундта өлетінін анықтаңыз.

Енгізу

Бірінші жолда бір бүтін сан \(t\) \((1 \leq t \leq 1000)\) — тестілердің саны.

Келесі \(t\) жолдың әрқайсысында бір бүтін сан \(h\) \((1 \leq h \leq 10^9)\) — қаһарманның бастапқы денсаулық ұпайлары.

Шығару

Әр тест үшін қаһарманның қай раундта өлетінін көрсететін бір бүтін санды шығарыңыз.

Мысалдар

Енгізу 1

5
1
2
10
7
500

Жауап 1

2
3
5
5
18

Ескертпелер

Үшінші мысал. Қаһарман \(h = 10\) денсаулық ұпайымен бастайды:

• Раунд 1: \(10\) \(1\)-ге бөлінеді, критикалық соққы: \(h = 10/1 = 10\)

• Раунд 2: \(10\) \(2\)-ге бөлінеді, критикалық соққы: \(h = 10/2 = 5\)

• Раунд 3: \(5\) \(3\)-ке бөлінбейді, жарақатпен жеңіс: \(h = 5-1 = 4\)

• Раунд 4: \(4\) \(4\)-ке бөлінеді, критикалық соққы: \(h = 4/4 = 1\)

• Раунд 5: \(1\) \(5\)-ке бөлінбейді, жарақатпен жеңіс: \(h = 1-1 = 0\)