시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 90 21 19 43.182%

문제

상근이의 취미는 두들이다. 두들을 하려면 모눈종이가 필요하다. 두들은 가장 왼쪽 위 칸 (0,0)에서 시작한다. 매번 칸에 방문할 때 마다 상근이는 칸에 X를 채운다. (0,0)을 채운 다음에는 한 칸 오른쪽, 아래 (1,1)로 이동해서 X를 채운다. 이렇게 채워나가다가 종이의 모서리를 만나면, 반대방향으로 진행하고, 시작점으로 돌아올때까지 계속해서 X를 표시한다.

종이의 크기가 주어졌을 때, X를 표시한 서로 다른 칸의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 모눈종이의 높이와 너비(칸의 수)가 주어진다. 두 숫자는 모두 2보다 크거나 같고, 20000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스 마다, X를 채운 서로 다른 칸의 수를 출력한다.

예제 입력 1

3
11 3
5 7
5 8

예제 출력 1

11
12
20

힌트

W3sicHJvYmxlbV9pZCI6IjUwMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOTlcdWMxMWMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG9vZGxlLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMjBweDsgd2lkdGg6Mjc5cHhcIiBcLz5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZGU4XHViYmY4XHViMjk0IFx1YjQ1MFx1YjRlNFx1Yzc3NFx1YjJlNC4gXHViNDUwXHViNGU0XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWI0NTBcdWI0ZTRcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4ICgwLDApXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1Y2U3OFx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTc4XHVjNWQwIFhcdWI5N2MgXHVjYzQ0XHVjNmI0XHViMmU0LiAoMCwwKVx1Yzc0NCBcdWNjNDRcdWM2YjQgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1ZDU1YyBcdWNlNzggXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM1NDRcdWI3OTggKDEsMSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTc0XHVjMTFjIFhcdWI5N2MgXHVjYzQ0XHVjNmI0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjYzQ0XHVjNmNjXHViMDk4XHVhYzAwXHViMmU0XHVhYzAwIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJhYThcdWMxMWNcdWI5YWNcdWI5N2MgXHViOWNjXHViMDk4XHViYTc0LCBcdWJjMThcdWIzMDBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOWM0XHVkNTg5XHVkNTU4XHVhY2UwLCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjJjXHViNTRjXHVhZTRjXHVjOWMwIFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBYXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODg1XHVjNzc0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBYXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjIwOFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHViMTA4XHViZTQ0KFx1Y2U3OFx1Yzc1OCBcdWMyMTgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJhYThcdWI0NTAgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAyMDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFhcdWI5N2MgXHVjYzQ0XHVjNmI0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjZTc4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTAyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRvb2RsaW5nIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Rvb2RsZS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MjIwcHg7IHdpZHRoOjI3OXB4XCIgXC8+V2hlbiB0aGlua2luZyBhYm91dCBhIGhhcmQgcHJvYmxlbSBhIGxvdCBvZiBwZW9wbGUgbGlrZSB0byBkb29kbGUsIHRvIGNyZWF0ZSAmcXVvdDthbiB1bmZvY3VzZWQgZHJhd2luZyB0aGF0IGNhbiBoZWxwIHRoZSBtZW1vcnkgYW5kIGltcHJvdmUgYWJzdHJhY3QgdGhpbmtpbmcmcXVvdDsuIFRoZSBtb3N0IGJhc2ljIGZvcm0gb2YgZG9vZGxlIGlzIGEgcmVwZXRpdGl2ZSBwYXR0ZXJuIGNvdmVyaW5nIHRoZSB3aG9sZSBwYWdlLiBPbmUgd2F5IHRvIGNyZWF0ZSBzdWNoIGEgcGF0dGVybiBpcyB0byB0YWtlIGEgZ3JhcGhpbmcgcGFwZXIgYW5kIHN0YXJ0IGluIHRoZSB0b3AtbGVmdCBjb3JuZXIgKDA7IDApIGFuZCBmaWxsIG91dCB0aGUgc3F1YXJlLCB0aGVuIG1vdmUgZG93biBhbmQgcmlnaHQgb25lIHNxdWFyZSAoMSwgMSksIGZpbGwgaXQgb3V0LCBhbmQgc28gb24uIEV2ZXJ5IHRpbWUgeW91IGhpdCB0aGUgZWRnZSBvZiB0aGUgcGFwZXIgeW91IHJldmVyc2UgZGlyZWN0aW9uLCB1bnRpbCB5b3UgYXJlIGJhY2sgYXQgdGhlIHN0YXJ0aW5nIHBvaW50LiBUaGlzIHdpbGwgY3JlYXRlIGEgdmVyeSBzb290aGluZyBwYXR0ZXJuLjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0byBlbnN1cmUgeW91IGRvbiYjMzk7dCBzcGVuZCB0aGUgd2hvbGUgY29tcGV0aXRpb24gZG9vZGxpbmcgeW91IG5lZWQgdG8gZmlndXJlIG91dCBob3cgbWFueSBzcXVhcmVzIHlvdSB3aWxsIGhhdmUgdG8gZmlsbCBpbiB0aGUgcGFwZXIgdG8gY29tcGxldGUgdGhlIGRvb2RsZSBiZWZvcmUgeW91IGV2ZW4gc3RhcnQgZG9vZGxpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4xICZsZTsgbiAmbGU7IDQwMDA8XC9wPlxyXG5cclxuPHA+VGhlIG51bWJlciBvZiB0ZXN0Y2FzZXM8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggbjo8XC9wPlxyXG5cclxuPHA+MiAmbGU7IHgsIHkgJmxlOyAyMDAwMDxcL3A+XHJcblxyXG48cD5UaGUgaGVpZ2h0IGFuZCB3aWR0aCAoaW4gc3F1YXJlcykgb2YgdGhlIGdyYXBoaW5nIHBhcGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBudW1iZXIgb2YgdW5pcXVlIHNxdWFyZXMgeW91IHdpbGwgaGF2ZSBsbGVkIGluIGJlZm9yZSB5b3UgYXJlIGRvbmUgd2l0aCB5b3VyIGRvb2RsZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d