A well known result in number theory is that every non-negative integer can be represented as the sum of four squares of non-negative integers.

You are given a non-negative integer $n$. Your task is to find four non-negative integers $a$, $b$, $c$ and $d$ such that $n = a^2 + b^2 + c^2 + d^2$.

Input

The first line has an integer $t$: the number of test cases.

Each of the next $t$ lines has an integer $n$.

Output

For each test case, print four non-negative integers $a$, $b$, $c$ and $d$ that satisfy $n = a^2 + b^2 + c^2 + d^2$.

Constraints

• $1 \le t \le 1000$
• $0 \le n \le 10^7$
• the sum of all $n$ is at most $10^7$

Example

Input:

3
5
30
322266

Output:

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