Cho hai số nguyên n và m. Hãy tính số lượng số nguyên x thỏa:

$$ 0 \le x \le m $$ $$ gcd(n + x, m) = gcd(n, m) $$

Input

Dòng đầu tiên là số nguyên t (~ 1 \le t \le 10 ~) - số lượng test case

Tiếp theo là t dòng gồm 2 số nguyên n và m

50% điểm: (~ 1 \le n, m \le 10^{6} ~)

50% điểm: (~ 10^{6} \le n, m \le 10^{12} ~)

Output

Một dòng duy nhất là số lượng số nguyên x thỏa mãn yêu cầu đề bài.

Examples

Input

3 
3 5 
3 6 
8 10 

*Output *

5
2
5 

*Giải thích test 1: * Các số thỏa mãn là: 0, 1, 3, 4, 5

*Giải thích test 2: * Các số thỏa mãn là: 0, 6

*Giải thích test 3: * Các số thỏa mãn là: 0, 4, 6, 8, 10