Bạn được cho 2 số nguyên dương \(a, b\) \((a<b)\). Hãy tính số các số x thỏa mãn \(0\leq x <b\) và \(\gcd(a,b)=\gcd(a+x,b)\).

\(\gcd(x,y)\): Ước chung lớn nhất của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa \(t\) \((1 \leq t \leq 50)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a, b \leq 10^{10})\).

Output

• Ứng với mỗi câu hỏi in ra số \(x\) cần tìm.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \((1 \leq a, b \leq 1000)\);
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

3
4 9
5 10
42 9999999967 

6
1
9999999966