ROOT - Root of a Linear Equation

Given two nonnegative integers a and b, you are to generate the solution of the equation b*x=a.

Input

The number of test cases is given in the very first line. For each test case there is a single line containing two integers a and b without any leading zeroes, separated by a single space.

Tip: For more than 95% of test cases, int in C/C++/Java or longint in Pascal is enough.

The input file is about 1.4 KB.

Output

For each test case, output a single line containing the root in decimal cyclic notations, or "Invalid Input!!!"(without quotes) if the solution is not unique or the solution doesn't exist. See the example for more details.

The output file is about 1.3MB.

Example

Input:
8
1 1
1 2
1 3
1 4
1 6
24 2
15 7
1 89

Output:
1.0
0.5
0.(3)
0.25
0.1(6)
12.0
2.(142857)
0.(01123595505617977528089887640449438202247191)

Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:UVA 942; USACO 79; test data by Blue Mary

hide comments
2019-02-10 09:06:56
@Aditya Paliwal No, use python or boost library in c++
2018-08-11 21:01:16
if the answer is 0, do you output 0 or 0.0?
2014-12-24 09:35:34 Aditya Paliwal
Can a and b fit in 64 bit integers?
2014-11-24 14:23:42 [Lakshman]
May I have a case where we have to print Invalid Input!!!. Thanks.
--ans(Francky)--> I don't think it's a spoil to say that 0*x=1 does not have a solution...

Finally AC . Thanks I was missing 0 0 condition.

Last edit: 2014-11-24 18:45:04
2014-11-14 04:44:14 [Lakshman]
What is the expected complexity.
Thanks.
2014-04-17 12:22:51 Bharath Reddy
Finally AC :)
'b' can be equal to zero. Got NZEC twice because of this.

Last edit: 2014-04-28 13:05:46
2012-06-08 02:27:06 testing
how can we know that the solution in not unique, I am getting WA :( thanks
2012-06-02 12:08:46 (Tjandra Satria Gunawan)(曾毅昆)
The output file is LARGER than 1.3MB :(
2011-07-12 12:59:41 ASEMBL
a,b will be bigger than 1e18.....
2010-06-01 03:47:44 Ravi Kiran
Very strict test data.
Tough Sum!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.