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 math\nimport itertools\nimport heapq\nfrom sys import stdin, stdout, setrecursionlimit\nfrom bisect import bisect, bisect_left, bisect_right\nfrom collections import defaultdict, deque\n \n \n# d = defaultdict(lambda: 0)\n# setrecursionlimit(10**7)\n# inf = float("inf")\n \n \n##### stdin ####\ndef LM(t, r): return list(map(t, r))\ndef R(): return stdin.readline()\ndef RS(): return R().split()\ndef I(): return int(R())\ndef F(): return float(R())\ndef LI(): return LM(int,RS())\ndef LF(): return LM(float,RS())\ndef ONE_SL(): return list(input())\ndef ONE_IL(): return LM(int, ONE_SL())\ndef ALL_I(): return map(int, stdin)\ndef ALL_IL(): return LM(int,stdin)\n \n##### tools #####\ndef ap(f): return f.append\ndef pll(li): print(\'\\n\'.join(LM(str,li)))\ndef pljoin(li, s): print(s.join(li))\n \n \n \n##### main #####\n \nclass BIT(object):\n \n\tdef __init__(self,l):\n\t\tself.size = l\n\t\tself.bit = [0]* (self.size+1)\n \n\tdef sum(self, i):\n\t\ts = 0\n\t\twhile i > 0:\n\t\t\ts += self.bit[i]\n\t\t\ti -= i & -i\n\t\treturn s\n \n\tdef add(self, i, x):\n\t\twhile i < self.size:\n\t\t\tself.bit[i] += x\n\t\t\ti += i & -i\n \n\tdef __str__(self):\n\t\treturn str(self.bit)\n \n \ndef main():\n\tN,M = LI()\n \n\tbit = BIT(M+2)\n\tL = []\n\tR = []\n\tb = [[] for i in range(M+1)]\n \n \n\tfor i in range(N):\n\t\tl,r = LI()\n\t\tL.append(l); R.append(r)\n\t\tb[r-l +1].append(i)\n \n \n\tgone = 0\n\tfor d in range(1, M+1):\n\t\tfor i in b[d]:\n\t\t\tgone+=1\n\t\t\tbit.add(L[i], 1)\n\t\t\tbit.add(R[i]+1, -1)\n \n \n\t\tans = N-gone\n \n\t\tfor m in range(d, M+1, d):\n \n\t\t\tans += bit.sum(m)\n\t\tprint(ans)\n \n \n \n \ndef __starting_point():\n\tmain()\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20991