У нас є \(N\)  кружечків і треба побудувати з них найбільш можливий квадрат. Потім з решти кружечків будуємо знову найбільший квадрат при можливості. І так далі. Для створення квадрата із стороною \(S\)  потрібно мати  \(S^2\) кружечків.

Знайдіть кількість квадратів, які можна побудувати за описаними правилами.

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

Перший рядок містить ціле число \(T\) (\(1 \le T \le 1000\)) - кількість тестів.

Потім слідують \(T\) рядків, кожен рядок містить ціле число \(N\) (\(1 \le N \le 1000\)).

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

Для кожного тесту в окремому рядку вивести шукану кількість квадратів.

Примітка

До прикладу 1:

До тесту 1:

Складаємо квадрат зі стороною 9, використовуючи 81 кружечок, а потім складаємо квадрат зі стороною 2, використовуючи решту 4.

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

2
85
114

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

2
4