시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB165514433.588%

문제

연돌이는 세순이에게서 경운기를 훔쳐서 좌표평면으로 나왔다! 하지만 연돌이는 운전을 끔찍하게 못해서 다음 규칙에 의해서만 움직일 수 있다:

  1. 각 움직임은 x축 양의 방향이나 y축 양의 방향에 평행해야 한다.
  2. n번째 움직임은 선택한 방향으로 2^(n - 1) 칸만큼 움직인다.

연돌이가 있는 평면은 (0, 0), (A, 0), (0, B), (A, B)를 꼭짓점으로 가지는 직사각형 모양이다. 연돌이가 (0, 0)에서 출발한다고 할 때 평면의 경계를 포함하여 연돌이가 방문할 수 있는 좌표의 종류는 몇 가지인가?

입력

첫 줄에는 테스트 케이스의 수 T(0 ≤ T ≤ 100)이 입력된다. 이어지는 N줄에 걸쳐 두 정수 A, B(1 ≤ A, B ≤ 108)이 입력된다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 연돌이가 N번째 평면에서 도달할 수 있는 좌표의 종류를 출력한다.

첫 테스트 케이스에서 연돌이는 (0, 0), (0, 1), (1, 0), (1, 2), (2, 1), (0, 3)에 방문하는 것이 가능하다.

예제 입력 1

2
2 3
7 7

예제 출력 1

6
15
W3sicHJvYmxlbV9pZCI6IjEwNDc3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2JkXHVjNmI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZjBcdWIzY2NcdWM3NzRcdWIyOTQgXHVjMTM4XHVjMjFjXHVjNzc0XHVjNWQwXHVhYzhjXHVjMTFjIFx1YWNiZFx1YzZiNFx1YWUzMFx1Yjk3YyBcdWQ2ZDRcdWNjZDBcdWMxMWMgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1YzY1NFx1YjJlNCEgXHVkNTU4XHVjOWMwXHViOWNjIFx1YzVmMFx1YjNjY1x1Yzc3NFx1YjI5NCBcdWM2YjRcdWM4MDRcdWM3NDQgXHViMDU0XHVjYzBkXHVkNTU4XHVhYzhjIFx1YmFiYlx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGMgXHVhZGRjXHVjZTU5XHVjNWQwIFx1Yzc1OFx1ZDU3NFx1YzExY1x1YjljYyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNDo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWFjMDEgXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQwIHhcdWNkOTUgXHVjNTkxXHVjNzU4IFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjA5OCB5XHVjZDk1IFx1YzU5MVx1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+blx1YmM4OFx1YzlmOCBcdWM2YzBcdWM5YzFcdWM3ODRcdWM3NDAgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyAyXihuIC0gMSkgXHVjZTc4XHViOWNjXHVkMDdjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM1ZjBcdWIzY2NcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDNjOVx1YmE3NFx1Yzc0MCAoMCwgMCksIChBLCAwKSwgKDAsIEIpLCAoQSwgQilcdWI5N2MgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzNjXHViODVjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0LiBcdWM1ZjBcdWIzY2NcdWM3NzRcdWFjMDAgKDAsIDApXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIFx1YzVmMFx1YjNjY1x1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWM3NTggXHVjODg1XHViOTU4XHViMjk0IFx1YmE4NyBcdWFjMDBcdWM5YzBcdWM3NzhcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQoMCAmbGU7Jm5ic3A7VCAmbGU7IDEwMClcdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBBLCBCKDEgJmxlOyZuYnNwO0EsIEIgJmxlOyZuYnNwOzEwPHN1cD44PFwvc3VwPilcdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzVmMFx1YjNjY1x1Yzc3NFx1YWMwMCBOXHViYzg4XHVjOWY4IFx1ZDNjOVx1YmE3NFx1YzVkMFx1YzExYyBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWM3NTggXHVjODg1XHViOTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgXHVjNWYwXHViM2NjXHVjNzc0XHViMjk0ICgwLCAwKSwgKDAsIDEpLCAoMSwgMCksICgxLCAyKSwgKDIsIDEpLCAoMCwgMylcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA0NzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmFjdG9yIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgdGhlIENvdyBoYXMgc3RvbGVuIEZhcm1lciBKb2huJnJzcXVvO3MgdHJhY3RvciBhbmQgaXMgcnVubmluZyB3aWxkIG9uIHRoZSBjb29yZGluYXRlIHBsYW5lISBTaGUsIGhvd2V2ZXIsIGlzIGEgdGVycmlibGUgZHJpdmVyLCBhbmQgY2FuIG9ubHkgbW92ZSBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FYWNoIG9mIGhlciBtb3ZlbWVudHMgaXMgaW4gdGhlIHNhbWUgZGlyZWN0aW9uIGFzIGVpdGhlciB0aGUgcG9zaXRpdmUgeC1heGlzIG9yIHRoZSBwb3NpdGl2ZSB5LWF4aXMuPFwvbGk+XHJcblx0PGxpPkhlciBudGggbW92ZW1lbnQgdGFrZXMgaGVyIDI8c3VwPm4mbWludXM7MTxcL3N1cD4gdW5pdHMgZm9yd2FyZCBpbiBoZXIgY2hvc2VuIGRpcmVjdGlvbi4gKE9uIGhlciBmaXJzdCBtb3ZlbWVudCwgbiA9IDEsIHNvIHNoZSBtb3ZlcyAxIHVuaXQuKTxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZhcm1lciBKb2huJnJzcXVvO3MgZmFybSBpcyBvbiB0aGUgY29vcmRpbmF0ZSBwbGFuZSwgaW4gdGhlIHNoYXBlIG9mIGEgcmVjdGFuZ2xlIHdpdGggY29ybmVycyBhdCAoMCwgMCksIChBLCAwKSwgKDAsIEIpIGFuZCAoQSwgQikuIElmIEJlc3NpZSBzdGFydHMgYXQgKDAsIDApLCBob3cgbWFueSBwb2ludHMgaW5zaWRlIHRoZSBmYXJtLCBpbmNsdWRpbmcgdGhlIGJvdW5kYXJ5LCBjb3VsZCBzaGUgcmVhY2g/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgYmVnaW5zIHdpdGggYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCkgb24gYSBsaW5lIGJ5IGl0c2VsZiwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdGhhdCBmb2xsb3cuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyAxMDxzdXA+ODxcL3N1cD4pLCBkZXNjcmliaW5nIHRoZSB1cHBlci1yaWdodCBjb3JuZXIgb2YgRmFybWVyIEpvaG4mcnNxdW87cyBmYXJtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBOIGxpbmVzLCB3aXRoIHRoZSBOdGggbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgcG9pbnRzIHRoYXQgQmVzc2llIGNvdWxkIHBvc3NpYmx5IHJlYWNoIGluIHRoZSBOdGggdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZmlyc3QgdGVzdCBjYXNlIG9mIHRoZSBzYW1wbGUsIEJlc3NpZSBjYW4gcmVhY2ggdGhlIGZvbGxvd2luZyBzaXggcG9pbnRzOiAoMCwgMCksICgwLCAxKSwgKDEsIDApLCAoMSwgMiksICgyLCAxKSBhbmQgKDMsIDApLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 I번

  • 문제의 오타를 찾은 사람: eric00513
  • 문제를 번역한 사람: tae
  • 문제를 만든 사람: Alexander Wei