Eva is playing a special game of “hide and seek” with Colin. Unlike the traditional game, Eva chooses a hidden positive integer $x$ for Colin to guess.

First, Eva tells Colin a positive integer $a$ and guarantees that $x\le a$.

Then Eva gives Colin $m$ constraints. Constraint $j$ consists of two non-negative integers $b_j$ and $c_j$ and requires

$$ b_j\bmod x=c_j. $$

Colin wants to enumerate every possible value of $x$, but he does not know how many there are. Determine the number of positive integers $x\le a$ that satisfy all the constraints.

It is guaranteed that at least one such integer exists.

Input

The first line contains two integers $m$ and $a$ ($1\le m\le 2\times 10^5,1\le a\le 10^9$), the number of constraints and the upper bound on $x$, respectively.

Each of the next $m$ lines contains two integers $b_j$ and $c_j$ ($0\le c_j\le b_j\le 10^9$), describing the constraint $b_j\bmod x=c_j$.

Output

Output one integer: the number of positive integers that satisfy all the given constraints.

Examples

Input 1

2 10
7 1
8 2

Output 1

2