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. Outp