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