Кухар випік \(N\) кексів, і тепер йому потрібно вирішити, скільки кексів помістити в пакет, якщо кожен пакет повинен містити однакову кількість кексів. Він вибере ціле число \(А\) від 1 до \(N\) включно, і в кожний пакет впакує точно \(А\) кексів. Кухар хоче впакувати якомога більше кексів у пакет. Після відправлення пакетів з кексами він з'їдає кекси, які залишилися — він дуже їх любить. Допоможіть йому вибрати такий розмір пакету \(А\), який дозволить з'їсти якомога більше кексів.

Формат вхідних даних

У першому рядку вхідного потоку міститься \(T\) \((1 ≤ T ≤ 1000)\)— кількість тестів.

У наступних рядках по одному числу \(N\) \((2 ≤ N ≤ 10^8)\) — кількість кексів.

Формат вихідних даних

Для кожного тесту виведіть такий розмір пакету, щоб кількість залишкових кексів була максимальною. Якщо для кількох розмірів пакету буде набрано однакову кількість залишкових кексів, то вивести найбільший розмір.

Приклад вхідних даних

2
2
5

Приклад вихідних даних

2
3