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 - w2) (x - w3) (x - w4) ... (x - w(n-1))

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

Input

The first line contains the number of test cases t. Then t lines follow each containing x and n, separated by a space.

Constraints

t ≤ 410

2 ≤ x ≤ 1000

2 ≤ n ≤ 1000

Output

Print the result of each 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