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 >
	David: 2020-05-21 16:17:50 Java time limit too strict. Pre-Compute polynomials in .05 sec and execute 10,000 large polynomial test cases in .45 sec - still get TLE here.
	(Tjandra Satria Gunawan)(曾毅昆): 2012-11-21 15:20:31 @[Retired] Blue.Mary: I do some precomputation O(50^2), after that, it can be solved with only O(k) ;-) I did that in python, but I don't know in java...
	[Rampage] Blue.Mary: 2012-11-21 07:54:00 I guess Java solution with time complexity O(k^2 * BigInteger Operation) can't pass? Edit: Pike/Java is so slow. O(k * BigInteger Operation) per test case almost gets TLE. Last edit: 2012-11-23 06:25:31
	Francky: 2012-11-04 18:26:07 I had a very poor/limited BigNum emulation for INCPOWK, so I had to build my first quite-complete attempt for this problem. It cost my some time, but I'm very happy to had this awesome problem to force me to do the job. Thanks to the author.
	Alex Anderson: 2012-10-13 00:58:53 Tanmay, there is a faster/better way to calculate the coefficients, if you still want to use them, though they aren't necessary to solve the problem. (Currently you are recalculating the same values a lot of times) And using BigInteger is fine, just be effective when you use it. EDIT: Tanmay, you are actually very close to solving the problem. There's one thing you can easily optimize, then AC. Last edit: 2012-10-13 01:32:00
	Francky: 2012-10-12 19:13:17 @Tanmay : you don't need those coefficients. Try to manage without them.
	Tanmay: 2012-10-12 16:11:32 TLE :( Even after optimizing a LOT. <spoiler> Mostly because I still don't know how to find binomial coefficients without using BigInteger in Java. </spoiler>
	:D: 2012-10-08 06:56:47 Another chapter in my book "Failing with Python 101" :) I guess I was missing some vital optimization. I wouldn't blame it on the problem though. It was great!
	(Tjandra Satria Gunawan)(曾毅昆): 2012-10-08 03:52:39 seems that my BigInt algo in C is very slow :-( I still need 2x this (lower bound) time limit to get Accepted in C. Last edit: 2012-10-08 04:11:27
	Alex Anderson: 2012-10-08 01:01:44 Efficiency is still good, but it wasn't my intention to make things require micro-optimizations so I'll raise the time bounds a bit. Some "random" sampling of submissions that already were done showed correct answers for several that had previously timed out, some were wrong, and some still timed out. I've raised the time limit by a factor of 2. I'm not sure how to account for such variance in the runtimes, so I suppose guesswork will have to do. Last edit: 2012-10-08 01:02:29