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.
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
for each query print the number of lucky shirts Alal has.
Input | Output |
---|---|
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.