Somnath is a rich farmer and a rational family guy. He has a huge plot of land under his attorney and since he has grown old he has decided to divide this land equally among his children.He has called Pritha to help him in efficiently dividing the plot. Pritha comes and measures the plot to find that it is a MxN rectangular plot constructed from MxN unit square lands. Somnath has told Pritha that he has MxN children. To split the land, Pritha can cut it in vertical or horizontal direction(through the lines that separate the squares). Then , she should do the same with each part separately until she reaches MxN unit size plots of the land.Now, Pritha has a lot of workload on her shoulders, so she seeks your help to find the minimum number of cuts required to accomplish this task. So basically your goal is to tell her the minimum number of cuts required to split all of the plot squares apart.
Input
The input consists of several test cases (1 ≤ T ≤ 106). In each line of input, there are two integers 1≤M≤300,the number of rows in the plot and 1≤N≤300, the number of columns in the plot.
Output For each line of input, your program should produce one line of output containing an integer indicating the minimum number of cuts needed to split the plot into unit size plots.
