You are given a positive integer N. Let us consider set A of fractions x/y where 0 <= x/y <= 1, y <= N and the maximum common divisor of x and y is 1.

For example N = 5. Set A in increasing order consists of elements 0/1; 1/5; 1/4; 1/3; 2/5; 1/2; 3/5; 2/3; 3/4; 4/5; 1/1.

Your task is to find the i-th smallest fraction in set A.

Input

The first line of input contains the number of testcases t (t <= 15). The first line of each testcase contains numbers N and M (N <= 5000, M <= 10000). The next M lines contain one question each.

Output

For each testcase, you should output M lines which are the answers to the M questions.

Example

Input:
1
5 4
1
3
5
8

Output:
0/1
1/4
2/5
2/3