# Practice on Toph

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

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

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.

70% Solution Ratio

sakibalaminEarliest,

sakibalaminFastest, 0.0s

dmehrab06Lightest, 3.6 MB

subhashis_cseShortest, 808B

Login to submit