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 Binclusive 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

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.