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 x2 + 1 represents the series 2, 5, 10, 17, .... . (Substituting value of x = 1, 2, 3, ... to get the values in the sequence)

Similarly x2 + 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 x2 + 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 x2 + 771401, only when x = 385700 then x2 + 771401 = 148765261401 = 3857012 is a perfect square. There are no other values of x for which x2 + 771401 will be a square.

This is because 771401 is difference between two consecutive squares 3857002 and 3857012 . So the infinite sequence represented by x2 + 771401 has only 1 perfect sqaure number when x = 385701.

Let us consider one more example x2 + 45, only when x = 2, 6 or 22 then x2 + 45 is a perfect square. So the infinite sequence represented by x2 + 45 has only 3 perfect sqaure numbers when x = 2, 6 or 22.

But infinite sequence represented by x2 + 46 contains no prefect square numbers, this because if it contains such a number then infinite sequence represented x2 + 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 x2 + 45 .

In other words given equation x2 + 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 x2 + 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 <= 106 

Sum of all 'n' in a test file will not exceed 106

Output

The output line has to printed for each test case line.

If there are finite number of values of 'x' for which x2 + 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 x2 + 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 x2 + 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: 2019-12-31 18:23:51

Happy New Year !

nadstratosfer: 2019-12-30 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: 2019-12-30 13:42:12

Happy New Year for great SPOJ community!

Last edit: 2019-12-30 16:05:56

Added by:Amitayush Thakur
Date:2019-12-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All