# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Phi Numbers in Range!

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**.

## 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** that are the number of phi numbers to be generated at first and the number of queries **(1<=N, M<=10 ^{5})**. 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** for each query in a new line. See the sample I/O for better understanding.

## Samples

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 |

Login to submit