題目描述

小明找到一個迷宮的地圖，迷宮呈現出方格狀的布局，大小爲n*m，每個路口都有寶藏。小明爲了避免危險，將臨近兩點之間的路程稱爲一條路，他希望可以走最少的路，幷拿到所有寶藏，請你算一算他最多可以不走幾條路。路是可以反復走的，只需要計算沒走過的路有幾條即可。

輸入格式

第一行輸入整數t(1<=t<=100)，意味著有t個測試數據

接下來t行，每行有n和m兩個整數(1<=n,m<=100)

輸出格式

共t行，第i行輸出第i個例子的答案

Samples

2
2 2
1 3

4
3

提示

上圖給出例子中2*2地圖的一種尋寶方案，灰色的綫條就是可以不經過的路，共4條

原始資料

• Zero1 題號：b078
• Hydro 題號：Z1078
• Locale：zh_TW
• Display：practice