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)

here 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 seprated by a space.

Constraints:

2<=x<=1000

2<=n<=1000

t<=410

Output

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

Example

Input:
1
5 10
Output:
9765624/4

warning: Time limit is too strict so optimise your solution as you can.First try the tuorial version of this http://www.spoj.com/problems/COMPLEX1/