Целая часть корня

Для каждого из $t$ чисел $n$ найдите наибольшее целое $k$ такое, что $k^2 \le n$.

Массива здесь нет — искать нужно по ответу.

В первой строке число $t$ $(1 \le t \le 10^5)$.

В каждой из следующих $t$ строк одно число $n$ $(0 \le n \le 10^{18})$.

Для каждого числа выведите ответ на отдельной строке.

Числа не помещаются в 32-битный тип, а произведение $k \cdot k$ может переполнить и 64-битный, если брать середину неаккуратно. Сравнивайте так, чтобы переполнения не возникало, — например, делением вместо умножения. Встроенной функции корня доверять не стоит: на больших числах она ошибается в последнем разряде.