Story: Twilight Sparkle was working on some formulas when she came across a strange pattern.

When she added 1/2 + 1/4 + 1/8 + ..., she saw that it kept getting closer and closer to 1.

She was able to figure out that problem and a few more, but there are others that are too difficult. She needs your help.

Problem Statement

Given k and r, integers, find

Sum from n = 1 to infinity of n^k / r^n.

Also you must output the exact value, as a fraction in lowest terms.

Input

You will be given a number T on the first line. The following T lines will be of the form

S k r

where S is a String label with no spaces, and both k and r are as described above.

Output

Your output will contain T lines of the form

S N / D

where S is the label you were given in the input, N is the numerator of the answer, and D is the denominator. D may be 1.

To be more precise, if the fraction is negative, then output the negative sign next to N.

Example

Input:
6
Case1: 0 2
Case2: 0 3
Case3: 0 -3
Label: 2 9
Otherlabel: 12 16
Biggest: 50 -555


Output:
Case1: 1 / 1
Case2: 1 / 2
Case3: -1 / 4
Label: 45 / 256
Otherlabel: 268201436794928 / 320361328125
Biggest: -71542844799237379223056641850683038399677651990786654293842285446351016224553939010
882650681431892067495137019178862799169155069446928707568453465 / 
7086055907083154841158073677533359179964732523333455695465110902606507148230087594593
20274728690683789654784801111318621847552

Note: The output for each case should all be on one line. It is split in the final case here for readability.

Bounds

T <= 10000

0 <= k <= 50

1 < |r| <= 1000

The timelimit per case is ~x5 my Java solution.

---

hide comments

< Previous 1 2 Next >
	Robert Gerbicz: 2012-10-08 01:01:44 Time limit is more than enough. Solved in c in 0.33 sec.
	Damian Straszak: 2012-10-08 01:01:44 finally accepted, but spent a lot of time on microoptimizations, didn't like it at all
	Damian Straszak: 2012-10-08 01:01:44 This is kind of annoying that doing one GCD per testcase results in TLE. Please consider changing the time limit. Also what consumes a lot of time is writing the output. What do you need this labels for? Last edit: 2012-10-07 20:40:03
	(Tjandra Satria Gunawan)(曾毅昆): 2012-10-08 01:01:44 Seems that it's impossible to solve this problem in C, or my BigInteger algo in C is very slow for division and modulo.. Last edit: 2012-10-07 16:17:36
	(Tjandra Satria Gunawan)(曾毅昆): 2012-10-08 01:01:44 I got AC after ~3.5 hours after I read the problem ;-) Well, I think this problem is very hard for C or other languages that not support big integer...
	(Tjandra Satria Gunawan)(曾毅昆): 2012-10-08 01:01:44 Wow, Very Nice problem, I'll try it \(^_^)/ Google + for your problem ;-)
	Francky: 2012-10-08 01:01:44 Here is a real problem, thanks for that. Last edit: 2012-10-06 20:41:14