PERFSQNUM  Yet Another Perfect Square Equation
Perfect squares are fairly simple concept. A number like 49 is perfect sqaure 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 infinte sequnece 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 infinte 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 sqaure 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 sqaure numbers when x = 2, 6 or 22.
But infinite sequence represented by x^{2} + 46 contains no prefect square numbers, this because if it contains such a number then infinite sequence represented x^{2} + 45 will not have any perfect sqaure 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 seperated by comma and space (, ) and enclosed within sqaure brackets. So for 'x^2 + 45' the output line will look like [2, 6, 22].
Incase 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".
Incase 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
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 