Добре відомий результат теорії чисел полягає в тому, що кожне невід'ємне ціле число можна представити у вигляді суми чотирьох квадратів невід'ємних цілих чисел.

Вам задано ціле невід'ємне число ~n~.

Ваше завдання — знайти чотири цілі невід'ємні числа ~a, b, c~ і ~d~, щоб ~n = a^2 + b^2 + c^2 + d^2~.

Обмеження

• ~1 \le t \le 1000~
• ~0 \le n \le 10^7~
• сума всіх ~n~ не більше ~10^7~

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

Перший рядок містить ціле число ~t~: кількість тестів.

Кожен із наступних ~t~ рядків містить ціле число ~n~.

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

Для кожного тесту виведіть чотири цілі невід'ємні числа ~a, b, c~ і ~d~, які задовольняють ~n = a^2 + b^2 + c^2 + d^2~.

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

3
5
30
322266

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

2 1 0 0
1 2 3 4
314 159 265 358