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 ith 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
hide comments
ashish kumar:
20151230 11:27:09
what should be time complexity ? 

numerix:
20141113 21:13:11
Problem has been switched from Pyramid to Cube cluster these days and time limit has been adjusted. It is too strict for slower languages, my former AC Python solution (using the no longer supported psyco module) does not pass anymore.


sarelfeniel:
20140119 03:19:05
Lots of fun and tons of optimisation to be had :D 

sumit agarwal:
20130603 13:56:04
the time constraint is very tight!!...an awesome question to learn how data types can also lead to TLE :) 

Divanshu:
20130328 12:39:08
Dont use C++ pair! Caused me 4 TLE's!! :( 

Haijun Deng:
20121226 14:07:10
Oh TLE :( 

Benjamin Pinaya:
20120306 01:33:09
Really nice one! It need a lot of optimization but it is awesome! 

Prakhar Jain:
20111222 06:19:35
Last edit: 20111222 08:59:56 

Jay Pandya:
20110715 08:51:39
the time limit is too strict!! after many tles...finally accepted... phewww 

Kunal Kapadia:
20110709 12:26:40
WDF!! gettin TLE again n again.... Even after knowing its Farey Sequence 
Added by:  Lê Đôn Khuê 
Date:  20050712 
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 