Snuke has decided to play a game, where the player runs a railway company.
There are M+1 stations on Snuke Line, numbered 0 through M.
A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train.
For example, if d = 3, the train stops at station 0, 3, 6, 9, and so forth.
There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations l_i, l_i+1, l_i+2, ..., r_i.
There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, ..., M.
For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0.
Here, assume that it is not allowed to change trains.

-----Constraints-----
 - 1 ≦ N ≦ 3 × 10^{5}
 - 1 ≦ M ≦ 10^{5}
 - 1 ≦ l_i ≦ r_i ≦ M

-----Input-----
The input is given from Standard Input in the following format:
N M
l_1 r_1
:
l_{N} r_{N}

-----Output-----
Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.

-----Sample Input-----
3 3
1 2
2 3
3 3

-----Sample Output-----
3
2
2

 - If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.
 - If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.
 - If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\ninput = sys.stdin.readline\n\nn, m = map(int,input().split())\nC = [list(map(int,input().split())) for i in range(n)]\n\nclass Bit:  # Fenwick Tree と同じ\n    def __init__(self, n):\n        self.size = n\n        self.tree = [0] * (n + 1)\n  \n    def sum(self, l, r):  # [l,r)の和を求める\n        # 内部的には[l+1,r+1)の和つまり(rまでの和-lまでの和)\n        s = 0\n        while r > 0:\n            s += self.tree[r]\n            r -= r & -r  # 2進数の最も下位の1を取り除くという意味(例:1010→1000)\n        while l > 0:\n            s -= self.tree[l]\n            l -= l & -l  # 2進数の最も下位の1を取り除くという意味(例:1010→1000)\n        return s\n  \n    def add(self, i, x):  # i番目にxを足す\n        i += 1\n        while i <= self.size:\n            self.tree[i] += x\n            i += i & -i  # 2進数の最も下位の1を繰り上げるという意味(例:1010→1100)\n\n    def sett(self, i, x):  # i番目をxにする\n        self.add(i, x - self.sum(i, i+1))\n\n    def print_bit(self): # 内部状態をindex順に出力\n        print([self.sum(i, i+1) for i in range(self.size)])\n\n    def print_sum(self): # 累積和をindex順に出力\n        print([self.sum(0, i+1) for i in range(self.size)])\n\n    def lower_bound_left(self, w):  # xまでの和がw以上となる最小のx、総和がw未満の場合nが返る\n        n = self.size\n        r = 1\n        x = 0\n        if self.sum(0, n) < w:\n            return n\n        while r < n:\n            r *= 2\n        le = r\n        while le > 0:\n            if (x + le < n and self.tree[x+le] < w):\n                w -= self.tree[x+le]\n                x += le\n            le //= 2\n        return x\n\n    def upper_bound_left(self, w):  # xまでの和がwより大きくなる最小のx、総和がw以下の場合nが返る\n        n = self.size\n        r = 1\n        x = 0\n        if self.sum(0, n) <= w:\n            return n\n        while r < n:\n            r *= 2\n        le = r\n        while le > 0:\n            if (x + le < n and self.tree[x+le] <= w):\n                w -= self.tree[x+le]\n                x += le\n            le //= 2\n        return x\n\n    def lower_bound_right(self, w):  # xまでの和がw以下となる最大のx、0番目がwより大きい場合-1が返る\n        return self.upper_bound_left(w) - 1\n\n    def upper_bound_right(self, w):  # xまでの和がw未満となる最大のx、0番目がw以上の場合-1が返る\n        return self.lower_bound_left(w) - 1\n\nD = [[] for i in range(m+1)]\nfor d in range(1, m+1):\n    for j in range(d, m+1, d):\n        D[j].append(d)\n\nL = [0] * (m+1)\nfor i in range(1, m+1):\n    for j in range(len(D[i])):\n        L[D[i][j]] = i\n\n# print(D)\n\nA = [-1] * (m+1)\nB = Bit(m+2)\nE = [0] * (m+1)\nANS = [0] * (m+1)\n\nC.sort(key=lambda x:x[1])\n# print(C)\nind = 0\n# mul = 1\nfor i in range(1, m+1):\n    # print(i)\n    for j in range(len(D[i])):\n        k = D[i][j]\n        if A[k] != -1:\n           ANS[k] += B.sum(0, A[k]+1)\n        E[i] += 1\n        A[k] = i\n        # print(E)\n    while ind < n and C[ind][1] <= i: \n        l = C[ind][0]\n        r = C[ind][1]\n        B.add(l, 1)\n        B.add(r+1, -1)\n        # mul -= 1\n        ind += 1\n\nfor i in range(1, m+1):\n    ANS[i] += B.sum(0, L[i]+1)\n\nfor i in range(1, m+1):\n    print(ANS[i])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14193