시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 95 24 22 46.809%

문제

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

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

입력

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

출력

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

예제 입력 1

3
11 3
5 7
5 8

예제 출력 1

11
12
20
W3sicHJvYmxlbV9pZCI6IjUwMjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOTlcdWMxMWMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG9vZGxlLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMjBweDsgd2lkdGg6Mjc5cHhcIiBcLz5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZGU4XHViYmY4XHViMjk0IFx1YjQ1MFx1YjRlNFx1Yzc3NFx1YjJlNC4gXHViNDUwXHViNGU0XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWI0NTBcdWI0ZTRcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4ICgwLDApXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1Y2U3OFx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTc4XHVjNWQwIFhcdWI5N2MgXHVjYzQ0XHVjNmI0XHViMmU0LiAoMCwwKVx1Yzc0NCBcdWNjNDRcdWM2YjQgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1ZDU1YyBcdWNlNzggXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM1NDRcdWI3OTggKDEsMSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTc0XHVjMTFjIFhcdWI5N2MgXHVjYzQ0XHVjNmI0XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjYzQ0XHVjNmNjXHViMDk4XHVhYzAwXHViMmU0XHVhYzAwIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJhYThcdWMxMWNcdWI5YWNcdWI5N2MgXHViOWNjXHViMDk4XHViYTc0LCBcdWJjMThcdWIzMDBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOWM0XHVkNTg5XHVkNTU4XHVhY2UwLCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjJjXHViNTRjXHVhZTRjXHVjOWMwIFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBYXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODg1XHVjNzc0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBYXHViOTdjIFx1ZDQ1Y1x1YzJkY1x1ZDU1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IG4oMSAmbGU7IG4gJmxlOyA0MDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViYWE4XHViMjA4XHVjODg1XHVjNzc0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWIxMDhcdWJlNDQoXHVjZTc4XHVjNzU4IFx1YzIxOClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCAyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDIwMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgWFx1Yjk3YyBcdWNjNDRcdWM2YjQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWNlNzhcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRG9vZGxpbmciLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG9vZGxlLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMjBweDsgd2lkdGg6Mjc5cHhcIiBcLz5XaGVuIHRoaW5raW5nIGFib3V0IGEgaGFyZCBwcm9ibGVtIGEgbG90IG9mIHBlb3BsZSBsaWtlIHRvIGRvb2RsZSwgdG8gY3JlYXRlICZxdW90O2FuIHVuZm9jdXNlZCBkcmF3aW5nIHRoYXQgY2FuIGhlbHAgdGhlIG1lbW9yeSBhbmQgaW1wcm92ZSBhYnN0cmFjdCB0aGlua2luZyZxdW90Oy4gVGhlIG1vc3QgYmFzaWMgZm9ybSBvZiBkb29kbGUgaXMgYSByZXBldGl0aXZlIHBhdHRlcm4gY292ZXJpbmcgdGhlIHdob2xlIHBhZ2UuIE9uZSB3YXkgdG8gY3JlYXRlIHN1Y2ggYSBwYXR0ZXJuIGlzIHRvIHRha2UgYSBncmFwaGluZyBwYXBlciBhbmQgc3RhcnQgaW4gdGhlIHRvcC1sZWZ0IGNvcm5lciAoMDsgMCkgYW5kIGZpbGwgb3V0IHRoZSBzcXVhcmUsIHRoZW4gbW92ZSBkb3duIGFuZCByaWdodCBvbmUgc3F1YXJlICgxLCAxKSwgZmlsbCBpdCBvdXQsIGFuZCBzbyBvbi4gRXZlcnkgdGltZSB5b3UgaGl0IHRoZSBlZGdlIG9mIHRoZSBwYXBlciB5b3UgcmV2ZXJzZSBkaXJlY3Rpb24sIHVudGlsIHlvdSBhcmUgYmFjayBhdCB0aGUgc3RhcnRpbmcgcG9pbnQuIFRoaXMgd2lsbCBjcmVhdGUgYSB2ZXJ5IHNvb3RoaW5nIHBhdHRlcm4uPFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIHRvIGVuc3VyZSB5b3UgZG9uJiMzOTt0IHNwZW5kIHRoZSB3aG9sZSBjb21wZXRpdGlvbiBkb29kbGluZyB5b3UgbmVlZCB0byBmaWd1cmUgb3V0IGhvdyBtYW55IHNxdWFyZXMgeW91IHdpbGwgaGF2ZSB0byBmaWxsIGluIHRoZSBwYXBlciB0byBjb21wbGV0ZSB0aGUgZG9vZGxlIGJlZm9yZSB5b3UgZXZlbiBzdGFydCBkb29kbGluZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjEgJmxlOyBuICZsZTsgNDAwMDxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVyIG9mIHRlc3RjYXNlczxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBuOjxcL3A+XHJcblxyXG48cD4yICZsZTsgeCwgeSAmbGU7IDIwMDAwPFwvcD5cclxuXHJcbjxwPlRoZSBoZWlnaHQgYW5kIHdpZHRoIChpbiBzcXVhcmVzKSBvZiB0aGUgZ3JhcGhpbmcgcGFwZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG51bWJlciBvZiB1bmlxdWUgc3F1YXJlcyB5b3Ugd2lsbCBoYXZlIGxsZWQgaW4gYmVmb3JlIHlvdSBhcmUgZG9uZSB3aXRoIHlvdXIgZG9vZGxlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=