Mỗi chú bò của Nông dân John đều muốn tìm tri kỷ — một chú bò khác có những đặc điểm tương tự và tương hợp với mình nhất. Tính cách của mỗi chú bò được mô tả bằng một số nguyên \(p_i\) (\(1\le p_i\le 10^{18}\)). Hai chú bò có cùng tính cách là tri kỷ. Một chú bò có thể thay đổi tính cách bằng một “phép thay đổi”: nhân với \(2\), chia cho \(2\) (nếu \(p_i\) chẵn), hoặc cộng \(1\).

Ban đầu, Nông dân John ghép đôi những chú bò một cách tùy ý. Ông muốn biết cần bao nhiêu phép thay đổi để hai chú bò trong mỗi cặp trở thành tri kỷ. Với mỗi cặp, hãy xác định số phép thay đổi ít nhất mà chú bò thứ nhất trong cặp phải thực hiện để trở thành tri kỷ với chú bò thứ hai.

Dữ liệu vào

Dòng đầu chứa \(N\) (\(1\le N\le 10\)), là số cặp bò. Mỗi dòng trong \(N\) dòng còn lại mô tả một cặp bò bằng hai số nguyên chỉ tính cách của chúng. Số đầu tiên là tính cách của chú bò cần được thay đổi để khớp với chú bò thứ hai.

Dữ liệu ra

In \(N\) dòng. Với mỗi cặp, in số phép toán ít nhất cần thiết để chú bò thứ nhất biến đổi tính cách của mình thành tính cách của chú bò thứ hai.

Phân nhóm

• Các test 1–4 thỏa mãn \(p_i\le 10^5\).
• Các test 5–12 không có ràng buộc bổ sung.

Ví dụ

6
31 13
12 8
25 6
10 24
1 1
997 120

8
3
8
3
0
20

Nguồn

USACO 2022 January Contest, Silver — Searching for Soulmates: https://usaco.org/index.php?page=viewproblem2&cpid=1182

Tác giả: Quanquan Liu.