Gats's Universal Necklaces

Time limit: 2000 msMemory limit: 256 MB

Gats is preparing necklaces from several designs. Design $i$ contains two strings with $A_i$ and $B_i$ ordinary beads, together with a connector containing $C_i$ beads.

For a chosen positive integer target size $d$ , Gats removes as many complete groups of $d$ beads as possible from each ordinary string. The two strings therefore leave $A_i \bmod d$ and $B_{}$ beads.

Design $i$ closes perfectly at size $d$ exactly when $(A_i \bmod d)+(B_i \bmod d)+C_i=d.$

A size $d$ is universal if every one of the $N$ designs closes perfectly at that size.

For each of $Q$ queries, determine how many universal integer sizes belong to the given inclusive interval.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N \le 10^4$ , $1 \le Q \le 2\cdot 10^5$ ), the number of necklace designs and the number of queries.

Output

For each query $j$ , print one integer: the number of universal positive integer sizes $d$ satisfying $L_j \le d \le R_j$ .

Samples

Sample 1

Input

Output

1
0
2

The universal necklace sizes are $5$ and $15$ . The three query intervals contain one, zero, and two of these sizes, respectively.

Sample 2

Input

Output

0
1

With no ordinary beads on either string, the connector closes the design only when the target size is $7$ .

Gats's Universal Necklaces

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions