No submission language available for this problem.

Description

Input

The first line contains the single integer $T$ ($1 \le T \le 50$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1 \le a < m \le 10^{10}$).

Output

Print $T$ integers — one per test case. For each test case print the number of appropriate $x$-s.

Samples

3
4 9
5 10
42 9999999967

6
1
9999999966

Note

In the first test case appropriate $x$-s are $[0, 1, 3, 4, 6, 7]$.

In the second test case the only appropriate $x$ is $0$.