Có một hình chữ nhật MxN ô, mỗi lần ta được phép cắt hình chữ nhật thành hai hình chữ nhật con theo chiều ngang hoặc chiều dọc và lại tiếp tục cắt các hình chữ nhật con cho đến khi được hình vuông thì dừng. Hỏi có thể cắt hình chữ nhật MxN thành ít nhất bao nhiêu hình vuông.

Input:

Gồm nhiều dòng, mỗi dòng là một test là một cặp số M, N (1<=M, N <=100).

Output:

gồm một số dòng là kết quả tương ứng với dữ liệu vào.

Sample Input

2 4
6 8
3 1
1 2
10 1
7 3
1 3
2 6
10 2
3 2

Sample Output

2
4
3
2
10
5
3
3
5
3