$n$ хүн үдэшлэгт ирэв. Тэдгээрээс үдэшлэгт байгаа хүмүүс дунд нэг ч найзгүй хүмүүс үдэшлэгийг орхин явав. Дараа нь үлдсэн хүмүүс дунд яг нэг найзтай хүмүүс нь үдэшлэгийг орхин явав. Тэгээд энэ мэтчилэн үлдсэн хүмүүс дунд яг $2$, $3$, $...$, $n-1$ найзтай хүмүүс үдэшлэгийг орхин явав.

Энэ бүхний эцэст хамгийн ихдээ хэдэн хүн үдэшлэгт үлдэж болох вэ?

Оролт

Эхний мѳрѳнд тестийн тоо болох $t$ тоо $(1 ≤ t ≤ 10^5)$. Дараагийн $t$ ширхэг мѳр бүрт нэг бүхэл тоо $n$ ($1 ≤ n ≤ 10^5$) ѳгѳгднѳ.

Гаралт

Тест болгонд нэг мѳрѳнд үдэшлэгт үлдэж болох хамгийн их хүний тоог хэвлэ.