Karen has always been fascinated by perfect squares. They have so many interesting characteristics. She realized that since perfect squares altemate between even and odd numbers, any integer will have exactly one integer perfect square that is closest to it. That is, an integer is never halfway between two integer perfect squares. Your job is to take any integer in the range [1,1000000] and determine the closest integer perfect square to that number. Input: Input will consist of an integer N, the number of test cases. The number of test cases will be in range [1,20]. Each subsequent line will contain one integer in the range [1,1000000] Output: Each line of output will consist one number representing the closest integer perfect square to the input. Sample input: 5 90 91 144 500000 1111 Sample output: 81 100 144 499849 1089