COMPLEX1 - HELP ABHISHEK

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

IF your solution is fast enough then go for harder classical problem COMPLEX2


Added by:Abhishek Mishra
Date:2012-06-16
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2012-06-22 09:19:50 Avinash Mishra
nice implementation karatsuba algorithm
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.