Cho hai số nguyên dương \(X\) và \(Y\), đếm số lượng số nguyên \(K\) với \(0 \leq K < Y\) thỏa mãn \(\gcd(X,Y)=\gcd(X+K,Y)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \leq 100\));
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(X\) và \(Y\) (\(X,Y \leq 10^5\))

Output

• Ứng với mỗi câu hỏi in ra đáp số cần tìm.

Scoring

• Subtask 1 [\(40\%\)]: \(Y \leq 10^4\);
• Subtask 2 [\(60\%\)] Không ràng buộc gì thêm.

Example

1
3 15

4