FRACTION - Sort fractions

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

Added by:Lê Đôn Khuê
Date:2005-07-12
Time limit:2.5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Mr Nguyen Duc Thinh

hide comments
2010-07-18 17:05:43 premanandh_j
nice...

Last edit: 2010-07-18 17:13:39
2010-04-13 17:30:28 Sankalp Raghav
will the m questions be always in ascending order?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.