A. Найди массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Давайте назовем массив $$$a$$$, состоящий из $$$n$$$ положительных (больших, чем $$$0$$$) целых чисел, красивым, если для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется следующее условие: либо $$$a_i = 1$$$, либо хотя бы одно из чисел $$$a_i - 1$$$ и $$$a_i - 2$$$ присутствует в массиве.

Например:

  • массив $$$[5, 3, 1]$$$ — красивый: для $$$a_1$$$ число $$$a_1 - 2 = 3$$$ присутствует в массиве; для $$$a_2$$$ число $$$a_2 - 2 = 1$$$ присутствует в массиве; для $$$a_3$$$ выполняется условие $$$a_3 = 1$$$;
  • массив $$$[1, 2, 2, 2, 2]$$$ — красивый: для $$$a_1$$$ выполняется условие $$$a_1 = 1$$$; для каждого из остальных $$$a_i$$$ число $$$a_i - 1 = 1$$$ присутствует в массиве;
  • массив $$$[1, 4]$$$ — некрасивый: для $$$a_2$$$ ни числа $$$a_2 - 2 = 2$$$, ни числа $$$a_2 - 1 = 3$$$ нет в массиве, и $$$a_2 \ne 1$$$;
  • массив $$$[2]$$$ — некрасивый: для $$$a_1$$$ ни числа $$$a_1 - 1 = 1$$$, ни числа $$$a_1 - 2 = 0$$$ нет в массиве, и $$$a_1 \ne 1$$$;
  • массив $$$[2, 1, 3]$$$ — красивый: для $$$a_1$$$ число $$$a_1 - 1 = 1$$$ присутствует в массиве; для $$$a_2$$$ выполняется условие $$$a_2 = 1$$$; для $$$a_3$$$ чисдл $$$a_3 - 2 = 1$$$ присутствует в массиве.

Вам дано положительное целое число $$$s$$$. Найдите минимально возможный размер красивого массива, сумма элементов которого равна $$$s$$$.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

Затем следуют $$$t$$$ строк, $$$i$$$-я из которых содержит одно целое число $$$s$$$ ($$$1 \le s \le 5000$$$) для $$$i$$$-го набора входных данных.

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

Выведите $$$t$$$ целых чисел, $$$i$$$-е из них должно быть ответом на $$$i$$$-й набор входных данных (то есть должно быть равно минимально возможному размеру красивого массива с суммой элементов, равной $$$s$$$).

Пример
Входные данные
4
1
8
7
42
Выходные данные
1
3
3
7
Примечание

Рассмотрим пример из условия:

  1. в первом наборе входных данных массив $$$[1]$$$ удовлетворяет всем условиям;
  2. во втором наборе входных данных массив $$$[3, 4, 1]$$$ удовлетворяет всем условиям;
  3. в третьем наборе входных данных массив $$$[1, 2, 4]$$$ удовлетворяет всем условиям;
  4. в четвертом наборе входных данных массив $$$[1, 4, 6, 8, 10, 2, 11]$$$ удовлетворяет всем условиям.