# Practice on Toph

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

# Lucky Shirt

By backbencher16 · Limits 1s, 1.0 GB

Marjokes is a very famous comedy personality in Byteland. He is a poet, a writer, a singer and an actor. He is very fond of Shirts like his friend Alal. Alal wants to become a fortune-teller. He owns N shirts and each shirt has an unique ID from 1 to N. He found out that some shirt is lucky for him if it’s ID has exactly X number of co-primes which are less than or equal its ID. Two number i and j are co-primes if their Greatest Common Divisor is 1, GCD(i, j) = 1. You will be asked several queries, For each query find out How many lucky shirts he has in a range from A to B inclusive for a X.

## Input

You will be given the N,number of shirts he owns and Q, number of queries.In each query you will be given start point A,and end point B and value of X.

1≤N,Q,X≤100000

1≤A≤B≤100000

## Output

for each query print the number of lucky shirts Alal has.

## Sample

InputOutput
```10 2
1 10 2
5 9 6```
```3
2```

Explanation of sample test, There are 10 shirts. In first query you have to tell how many lucky shirt in 1 to 10 when x=2. Now 3,4 and 6 have exactly 2 coprimes. Coprimes of 3 are 1 and 2, coprimes of 4 are 1 and 3, coprimes of 6 are 1 and 5 . so the answer is 3. In the second query , 7 and 9 have exactly 6 coprimes ,so the answer is 2.

### Statistics

70% Solution Ratio

sakibalaminEarliest, 11M ago

sakibalaminFastest, 0.0s

dmehrab06Lightest, 3.6 MB

subhashis_cseShortest, 808B