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
2012-06-18 17:48:17 Alex Anderson
Optimize my solution? I just can't calculate the answer fast enough. Maybe I should solve MUL first, but it probably wouldn't help.

Last edit: 2012-06-17 07:45:46
2012-06-18 17:48:17 Abhishek Mishra
here 9765624/4 is the right one.
after solving the above sequence u will get the formula in form of numerator/denominator without reducing this form u have to answer it.
ryt answer is 9765624/4
here w is nth root of unity for example.
if n is 3 then roots are 1,(-1+i*3^(1/2))/2,(-1-i*3^(1/2))/2
2012-06-18 17:48:17 (Tjandra Satria Gunawan)(曾毅昆)
help me, I can't understand...
1) what is w? and is the output is value of w?
2) from test case above: 9765624/4=4882812/2=2441406/1=2441406 (which one is correct output?)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.