B. Раскрасить полоску
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Изначально есть массив нулей $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$.

Вы можете выполнять операции двух типов:

  1. Выбрать индекс $$$i$$$ такой, что $$$1 \le i \le n$$$ и $$$a_i = 0$$$, после чего записать в $$$a_i$$$ значение $$$1$$$;
  2. Выбрать индексы $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$, $$$a_l = 1$$$, $$$a_r = 1$$$ и $$$a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil$$$, после чего записать значение $$$1$$$ в $$$a_i$$$ для всех $$$l \le i \le r$$$.

За какое минимальное количество операций первого типа вы можете получить массив, все элементы которого равны единице?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массива.

Обратите внимание, что ограничение на сумму $$$n$$$ по всем наборам входных данных отсутствует.

Выходные данные

Для каждого набора входных данных выведите единственное число — минимальное количество операций первого типа.

Пример
Входные данные
4
1
2
4
20
Выходные данные
1
2
2
4
Примечание

В первом наборе можно выполнить операцию $$$1$$$-го типа с $$$i = 1$$$.

Во втором наборе можно выполнить следующую последовательность операций:

  1. Операция $$$1$$$-го типа, $$$i = 1$$$. После выполнения этой операции массив будет выглядеть так: $$$[1, 0]$$$.
  2. Операция $$$1$$$-го типа, $$$i = 2$$$. После выполнения этой операции массив будет выглядеть так: $$$[1, 1]$$$.
Последовательность операций во втором тесте

В третьем наборе можно выполнить следующую последовательность операций:

  1. Операция $$$1$$$-го типа, $$$i = 1$$$. После выполнения этой операции массив будет выглядеть так: $$$[1, 0, 0, 0]$$$.
  2. Операция $$$1$$$-го типа, $$$i = 4$$$. После выполнения этой операции массив будет выглядеть так: $$$[1, 0, 0, 1]$$$.
  3. Операция $$$2$$$-го типа, $$$l = 1$$$, $$$r = 4$$$. На данном отрезке $$$a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2$$$, что не меньше, чем $$$\lceil\frac{r - l + 1}{2}\rceil = 2$$$. После выполнения этой операции массив будет выглядеть так: $$$[1, 1, 1, 1]$$$.
Последовательность операций в третьем тесте