You are given a rectangular floor that is to be tiled with square tiles. The tiles come in a variety of sizes, but they all measure in some power of two: 1, 2, 4, 8, etc. A 5×6 space can be tiled with 30 of the smallest tile, but the minimum number of tiles required is only 9. Refer to the pattern below.
The input file DATA3.txt will contain 5 lines, where each line is a pair of integers 1 ≤ N, M ≤ 10000, separated by a space.
The output file OUT3.txt will contain 5 lines, the minimum number of tiles necessary to exactly cover the N-by-M space.
Sample Input:
10 5
1000 1001
21 13
9999 888
345 1277
Sample Output:
14
1358
42
4065
2046