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 = "# Binary Indexed Tree (Fenwick Tree)\n# 1-indexed\nclass BIT:\n  def __init__(self, n):\n    self.n = n\n    self.data = [0]*(n+1)\n    self.el = [0]*(n+1)\n  # sum(ary[:i])\n  def sum(self, i):\n    s = 0\n    while i > 0:\n      s += self.data[i]\n      i -= i & -i\n    return s\n  # ary[i]+=x\n  def add(self, i, x):\n    # assert i > 0\n    self.el[i] += x\n    while i <= self.n:\n      self.data[i] += x\n      i += i & -i\n  # sum(ary[i:j])\n  def get(self, i, j=None):\n    if j is None:\n      return self.el[i]\n    return self.sum(j) - self.sum(i)\n\n# 区間加算可能なBIT。内部的に1-indexed BITを使う\nclass BIT_Range():\n  def __init__(self,n):\n    self.n=n\n    self.bit0=BIT(n+1)\n    self.bit1=BIT(n+1)\n  # for i in range(l,r):ary[i]+=x\n  def add(self,l,r,x):\n    l+=1\n    self.bit0.add(l,-x*(l-1))\n    self.bit0.add(r+1,x*r)\n    self.bit1.add(l,x)\n    self.bit1.add(r+1,-x)\n  # sum(ary[:i])\n  def sum(self,i):\n    if i==0:return 0\n    #i-=1\n    return self.bit0.sum(i)+self.bit1.sum(i)*i\n  # ary[i]\n  def get(self,i):\n    return self.sum(i+1)-self.sum(i)\n  # sum(ary[i:j])\n  def get_range(self,i,j):\n    return self.sum(j)-self.sum(i)\n\ndef main1(n,m,lr):\n  lary=[[] for _ in range(m+1)]\n  for l,r in lr:\n    lary[r-l+1].append([l,r])\n  ret=[n]\n  bitr=BIT_Range(m+1)\n  cnt=0\n  for d in range(2,m+1):\n    for l,r in lary[d-1]:\n      cnt+=1\n      bitr.add(l,r+1,1)\n    tmp=n-cnt\n    dd=d\n    while dd<=m:\n      tmp+=bitr.get(dd)\n      dd+=d\n    ret.append(tmp)\n  return ret\n\ndef __starting_point():\n  n,m=map(int,input().split())\n  lr=[list(map(int,input().split())) for _ in range(n)]\n  print(*main1(n,m,lr),sep='\\n')\n\n__starting_point()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19821