# Phi Numbers in Range!

Codeware19: Intra AUST Pr...
Limits 5s, 1.0 GB

In number theory, Euler’s phi function, denoted as $ϕ(n)$, is an arithmetic function which counts the positive integers less than or equal to $P$ that are relatively prime to $P$. A number $X$ is relatively prime to $P$ if $GCD(X,P)=1$.For example, if $P = 10$, then there are 4 numbers, namely 1, 3, 7, 9 which are relatively prime to 10. Therefore, $ϕ(10)=4$.

In this problem, you have to answer $M$ number of queries of the form L R K. To answer the queries at first you have to generate an array $A$ consisting of first $N$ phi numbers. For example if $N=11$, then array $A$ will look like, $A=\{1,1,2,2,4,2,6,4,6,4,10\}$. For clarity, $ϕ(1)=1$, $ϕ(2)=1$, $ϕ(3)=2$, $ϕ(4)=2$, $ϕ(5)=4$, $ϕ(6)=2$, $ϕ(7)=6$, $ϕ(8)=4$, $ϕ(9)=6$, $ϕ(10)=4$, $ϕ(11)=10$.

For each query, you have to print the smallest $K$-th distinct phi number in the range $L$ to $R$. Say $L = 6$, $R = 11$, $K = 2$. Let $S$ denote the set of elements of array $A$ with its indices between 6 and 11. Then $S = \{2, 6, 4, 6, 4, 10\}$. The smallest 2nd distinct phi number = 4. What if $K = 3$? Answer is 6.

Notice that if $K = 5$ then there is no smallest $K$-th distinct phi number in that range. In such case, you have to print “No Distinct Phi Number” (w/o quotes).

## Input

At first, there will be an integer $T$ ($1 ≤ T ≤ 10$), which is the number of test cases. For each case, you will be given two positive integers $N$ and $M$ ($1 ≤ N, M ≤ 10^5$) that are the number of phi numbers to be generated at first and the number of queries. Then there will be $M$ lines each containing three numbers L R K ($1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ N$).

## Output

For each case print the case number in the first line like "Case x:" where $x$ is the number of the test case. Then output the smallest $K$-th distinct phi number or "No Distinct Phi Number" (w/o quotes) for each query in a new line.

## Sample

InputOutput
1
11 4
4 6 1
6 11 2
2 7 3
4 6 4

Case 1:
2
4
4
No Distinct Phi Number