In number theory, Euler’s phi function, denoted as , is an arithmetic function which counts the positive integers less than or equal to that are relatively prime to . A number is relatively prime to if .For example, if , then there are 4 numbers, namely 1, 3, 7, 9 which are relatively prime to 10. Therefore, .
In this problem, you have to answer number of queries of the form L R K
. To answer the queries at first you have to generate an array consisting of first phi numbers. For example if , then array will look like, . For clarity, , , , , , , , , , , .
For each query, you have to print the smallest -th distinct phi number in the range to . Say , , . Let denote the set of elements of array with its indices between 6 and 11. Then . The smallest 2nd distinct phi number = 4. What if ? Answer is 6.
Notice that if then there is no smallest -th distinct phi number in that range. In such case, you have to print “No Distinct Phi Number” (w/o quotes).
At first, there will be an integer (), which is the number of test cases. For each case, you will be given two positive integers and () that are the number of phi numbers to be generated at first and the number of queries. Then there will be lines each containing three numbers L R K
().
For each case print the case number in the first line like "Case x:" where is the number of the test case. Then output the smallest -th distinct phi number or "No Distinct Phi Number" (w/o quotes) for each query in a new line.
Input | Output |
---|---|
1 11 4 4 6 1 6 11 2 2 7 3 4 6 4 | Case 1: 2 4 4 No Distinct Phi Number |