An có hai hủ bi: Hủ \(1\) có \(a\) viên bi và Hủ \(2\) có \(b\) viên bi, và một hôm nhân trời trăng thanh gió mát, An đem \(2\) hủ bi này đến nhà Bình chơi, và đố Bình một bài toán như sau:

• Ở mỗi lượt chơi, Bình chọn một hủ bất kì và thực hiện \(1\) trong \(3\) phép toán sau:

• Nếu số lượng bi trong hủ đó chia hết cho \(2\), thì anh ta bốc \(\frac{1}{2}\) số bi trong hủ đó và đưa cho An nắm giữ

• Nếu số lượng bi trong hủ đó chia hết cho \(3\), thì anh ta bốc \(\frac{2}{3}\) số bi trong hủ đó và đưa cho An nắm giữ

• Nếu số lượng bi trong hủ đó chia hết cho \(5\), thì anh ta bốc \(\frac{4}{5}\) số bi trong hủ đó và đưa cho An nắm giữ

Và nhiệm vụ của Bình là hãy chơi sao cho số lượng bi ở hai hủ bằng nhau và dùng ít lượt chơi nhất !

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a,b(1\le a,b\le 10^9)\) - Thể hiện số bi ở hủ \(1\) và hủ \(2\)

Output

• Hãy in ra số lượt tối thiểu mà Bình cần dùng để thoả mãn yêu cầu bài toán mà An đưa ra, nếu không có cách nào thoả mãn thì in ra \(-1\). Còn nếu ban đầu số bi ở hai hủ đã bằng nhau thì in ra \(0\)

Example

2
3 6
2 8

1
2