ROBOT

Có $ N $ cửa, mỗi cửa có số $ x $ và màn hình hiển thị $ y $. Mỗi lần nhấn nút, $ y $ tăng 1. Cửa mở khi $ \gcd(x,y) > 1 $.

Yêu cầu: Tìm số lần nhấn ít nhất để mở mỗi cửa.

Input

Dữ liệu vào: File ROBOT.INP gồm:

• Dòng \(1\): $ N $ \(( 1 \leq N \leq 100 )\)
• $ N $ dòng tiếp theo: Mỗi dòng chứa $ x, y $ \(( 2 \leq x, y \leq 10^9 )\)

Output

Kết quả: File ROBOT.OUT chứa $ N $ số kết quả, mỗi số trên một dòng.

Example

3
10 8
13 11
10 3

0
2
1

Scoring

• \(30\%\) số test \(( N = 1, x,y \leq 10^5 )\) chiếm 30% điểm
• \(30\%\) số test \(( N \leq 100, x,y \leq 10^5 )\) chiếm 30% điểm
• \(40\%\) số test \(( N \leq 100, x,y \leq 10^9 )\) chiếm 40% điểm