$n$ математиков и трое программистов собираются ехать на поезде в другой город на конференцию. Они встречаются у кассы на вокзале. Первой подходит очередь программистов, и они, как все нормальные люди, покупают по билету на человека. Математики же покупают один билет на всех.

– Честно говоря, математики из вас так себе... – удивляются программисты.

– Не волнуйтесь! – бодро отвечают математики – У нас есть метод.

Перед отправлением поезда математики уже подготовились применить свой метод, но перед этим решили посмотреть, как расположились программисты. Оказалось, они взломали систему покупки билетов и купили билеты в СВ-вагон с собственным санузлом, разнообразным питанием и позолоченными креслами. И всё это по цене билетов в плацкарт! Глядя на эту роскошь, математикам стало стыдно за их метод, который заключался в том, чтобы набиться в один туалет и при подходе контроллёра высунуть руку с билетом.

– Ну как там ваш метод? - спросили информатики.

– Наш метод? – растерялись математики – Слушайте, а что мы всё о поездке да о поездке? Вот слабо вам... слабо вам... быстро посчитать, сколько простых чисел находится в промежутке между двумя натуральными числами $a_i$ и $b_i$ включительно? Воооот, дааа, давайте каждый из нас назовёт по одному такому диапазону, и на каждый диапазон вы должны быстро ответить, сколько в нём простых чисел! Да если хотите, мы можем даже не называть числа, превыщающие $k$! Вот тогда и выясним, кто круче!

Программисты, конечно, посмеялись этому вызову, но решили уделать математиков ещё и тут. Примерьте на себя роль этих программистов и напишите программу, которая отвечает на запросы математиков.

Входные данные

В первой строке находятся два числа $n$ и $k$ ($1 \le n \le 5 \cdot 10^5$, $1 \le k \le 10^6$) - количество математиков и максимальная граница запросов. Так как каждый математик делает по одному запросу, количество математиков равноценно количеству запросов.

В следующих $n$ строках записаны по два числа $a_i$ и $b_i$ - запрос $i$-того математика ($1 \le a_i, b_i \le k$).

Выходные данные

В ответ на каждый запрос с новой строки выведите количество простых чисел в промежутке между $a_i$ и $b_i$ включительно.

Подзадачи