COMPLEX2 - HELP ABHISHEK(version-II)

ABHISHEK is weak of mathematics he is not able to solve the sequences frequently. So he invited topcoders to develop a program for solving the sequence. He managed to solve the other kind of sequences except one kind.

The sequence description is as follows:

    (x-w)(x-w^2)(x-w^3)(x-w^4) ... (x-w^(n-1))

where x is a number and w is nth root of unity.

Input

first line contain number of test cases t. Then t line follow x and n. x and n separated by a space.

Constraints:

2 <= x <= 1000

2 <= n <= 1000

t <= 410

Output

Print the result per test case according to above sequence and also keep in mind if there is any term in decimal then write it in form of a fraction. see the I/O for further detail.

Example

Input:
1
5 10

Output:
9765624/4

Time limit is strict, so optimise your solution as you can. First try the tutorial version at COMPLEX1


Added by:Abhishek Mishra
Date:2012-06-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own

hide comments
2024-09-15 13:45:40
Did anyone get an AC using C++ without boost or similar library for big number arithmetic ?
2015-08-23 01:53:22 vishu
My first program in python \(^_^)/
2015-06-29 17:38:11 RIVU DAS
Nice question!
2013-06-06 23:20:51 Pranet Verma
will the numerator portion fit in 64 bits?

No

Last edit: 2013-06-12 13:46:40
2012-06-23 05:43:12 Anshu Avinash
Increase time limit to atleast 1s!I am stuck at 0.91s.
Finally AC :)

Last edit: 2012-06-23 06:29:18
2012-06-19 15:09:05 Abhishek Mishra
@jhanvi have you solved the sequence first.
if not then solve it u will reached to formula.
see my below comments..
2012-06-19 05:11:16 jaans
for which case we have to print num/den and for which whole number :O can't understand!!!plss help!
2012-06-18 17:48:17 Abhishek Mishra
@alex i saw ur solution you have use basic input/output by the way u r ryt we generally have to focus on questions rather than fast I/O.
yeah in some languages it's hard to submit the answer in case of c++ even the simpler cin/cout will do ur wrk..

Last edit: 2012-06-17 19:39:44
2012-06-18 17:48:17 Alex Anderson
I give up. I don't care about fast I/O, just solving the problem and I've done that. My I/O is fast enough, just not for this.
2012-06-18 17:48:17 Abhishek Mishra
use fast i/o
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.