Hạo và Huy đang chơi một trò chơi, mỗi người họ giữ một số nguyên dương, Hạo giữ số \(A\), Huy giữ số \(B\). Mỗi lượt chơi, mỗi người chơi được quyền chia số mình đang giữ cho một ước nguyên tố của nó hoặc không cần làm gì cả. Bạn hãy giúp Hạo và Huy tính số lượt chơi ít nhất để \(2\) con số của họ trở nên bằng nhau.

Input

• Dòng đầu chứa số nguyên dương \(T\) \((T \le 10^5)\) là số bộ dữ liệu cần xử lý.
• \(T\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(A\), \(B\) \((A,B \le 10^6)\) là con số ban đầu của Hạo và Huy

Output

• \(T\) dòng, mỗi dòng là đáp án của bộ dữ liệu thứ \(T\)

Constraints

• Có 25% số lượng test thỏa mãn \(T = 1\)
• Có 25% số lượng test khác thỏa mãn \(T \le 1000\)
• Có 50% số lượng test còn lại không có rang buộc gì thêm

Example

Sample input

3
1 1
2 1
6 5

Sample output

0
1
2