Sum of Four Squares

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