PERFSQNUM  Yet Another Perfect Square Equation
Perfect squares are fairly simple concept. A number like 49 is perfect square because it can be written as product of two same natural number i.e. 7 * 7.
On the other hand infinite sequence of numbers can be considered an intriguing concept, because it is not possible to represent all numbers belonging in an infinite sequence easily.
Can read more about infinite sequences here.
So one way to represent infinite sequence of numbers is to use an algebraic expression instead of writing all numbers in the sequence.
For example, expression x^{2} + 1 represents the series 2, 5, 10, 17 .... . (Substituting value of x = 1, 2, 3, ... to get the values in the sequence)
Similarly x^{2} + 4 represents the infinite series 5, 8, 13, 20, .... (Substituting value of x = 1, 2, 3, ... to get the values in the sequence)
Given an infinite sequence of numbers of form x^{2} + n, figuring out perfect square numbers within this sequence can be challenging even if checking a number is perfect square is easy.
For example, consider the infinite sequence represented by x^{2} + 771401, only when x = 385700 then x^{2} + 771401 = 148765261401 = 385701^{2} is a perfect square. There are no other values of x for which x^{2} + 771401 will be a square.
This is because 771401 is difference between two consecutive squares 385700^{2} and 385701^{2}. So the infinite sequence represented by x^{2} + 771401 has only 1 perfect square number when x = 385701.
Let us consider one more example x^{2} + 45, only when x = 2, 6 or 22 then x^{2} + 45 is a perfect square. So the infinite sequence represented by x^{2} + 45 has only 3 perfect square numbers when x = 2, 6 or 22.
But infinite sequence represented by x^{2} + 46 contains no perfect square numbers, this is because if it contains such a number then the infinite sequence represented x^{2} + 45 will not have any perfect square numbers which is a contradiction because we know 3 perfect square numbers contained in infinite sequence represented by x^{2} + 45.
In other words given equation x^{2} + n where n is a whole number (i.e. n can take values like 0, 1, 2, 3, 4 ...) find all x in ascending order such that x^{2} + n is a perfect square.
Input
The first line of input file contains a positive integer 't' and next 't' lines contains a string which looks like 'x^2 + n' (example 'x^2 + 3', 'x^2 + 5' etc.).
0 ≤ n ≤ 10^{6}
Sum of all 'n' in a test file will not exceed 10^{6}
Output
The output line has to printed for each test case line.
If there are finite number of values of 'x' for which x^{2} + n is a perfect square then print all such x in ascending order separated by comma and space (, ) and enclosed within square brackets. So for 'x^2 + 45' the output line will look like [2, 6, 22].
In case there are no such values of 'x' for which x^{2} + n is a perfect square then print "No Solution" (without quotes and case sensitive). So for 'x^2 + 46' the output line will be "No Solution".
In case there are infinitely many solutions for which x^{2} + n is a perfect square then print "Infinitely Many Solutions" (without quotes and case sensitive). So for 'x^2 + 0' the output line will be "Infinitely Many Solutions"
Example
Input: 3 x^2 + 45 x^2 + 0 x^2 + 46 Output: [2, 6, 22] Infinitely Many Solutions No Solution
hide comments
David:
20200731 21:27:35
Does x start at 0? In other words, is the solution for 25 "[0, 12]" or "[12]"?


tom_mega:
20191231 18:23:51
Happy New Year ! 

nadstratosfer:
20191230 18:47:52
Nice problem. I like how 3 lines of handling the I/O in Python grows to half the program in C ;) 

julkas:
20191230 13:42:12
Happy New Year for great SPOJ community! Last edit: 20191230 16:05:56 
Added by:  Amitayush Thakur 
Date:  20191229 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 