시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 538 219 188 43.519%

문제

강산이와 지현이는 모험 중에 어느 숲 속 깊숙히에서 신비한 동굴을 발견했다.

들떠서 동굴에 입장한 강산이와 지현이는 결국 동굴의 끝에서 거대한 금괴 하나를 발견했다.

하지만 둘이서 들고 나가기엔 금괴는 너무 거대하고 무거웠다.

방법이 없을까 고민하던 중, 지현이가 금괴에 숫자 n이 쓰여 있는 것을 발견했다.

그 순간 요정이 나타나 말했다.

  • 요정 : 이 금괴는 무거워. 이건 무려 2n 펨토그램인걸. 게다가 n은 62까지 갈 수 있다구.
  • 강산 : 어, 그렇다면 운이 좋은걸요! 지현이 가방은 정확히 a 펨토그램을 담을 수 있고, 제 가방은 b 펨토그램을 담을 수 있는데 이 때 a + b = 2n을 만족하니까요!
  • 지현 : 근데 어떻게 금괴를 자르지?
  • 요정 : 내 마법으로 어떤 물건이든 정확히 반토막을 낼 수 있어. 근데 난 마법을 하루에 한 번밖에 못 쓰는데..

강산이와 지현이는 며칠 후, 금괴를 모두 나눠 갖고 동굴을 나섰다.

이 때, 강산이와 지현이가 동굴을 나선 건 동굴에 들어온 뒤 며칠 뒤일까?

입력

입력의 첫 줄엔 테스트 케이스의 수 t ≤ 1000 가 주어진다.

그리고 t줄에 걸쳐, 정수 n, a, b가 주어진다. ( a, b ≥ 1, a + b = 2n, 1 ≤ n ≤ 62.)

출력

각 테스트 케이스마다 한 줄에 강산이와 지현이가 동굴을 최대한 빨리 떠났을 때 며칠이 지났는지 출력한다.

예제 입력 1

3
2 2 2
2 1 3
10 1000 24

예제 출력 1

1
2
7
W3sicHJvYmxlbV9pZCI6IjEwMjc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2U4XHViNGRjIFx1YjdlY1x1YzJkYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhYzE1XHVjMGIwXHVjNzc0XHVjNjQwIFx1YzljMFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWJhYThcdWQ1ZDggXHVjOTExXHVjNWQwIFx1YzViNFx1YjI5MCBcdWMyMzIgXHVjMThkIFx1YWU0YVx1YzIxOVx1ZDc4OFx1YzVkMFx1YzExYyBcdWMyZTBcdWJlNDRcdWQ1NWMgXHViM2Q5XHVhZDc0XHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNGU0XHViNWEwXHVjMTFjIFx1YjNkOVx1YWQ3NFx1YzVkMCBcdWM3ODVcdWM3YTVcdWQ1NWMgXHVhYzE1XHVjMGIwXHVjNzc0XHVjNjQwIFx1YzljMFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjYjBcdWFkNmQgXHViM2Q5XHVhZDc0XHVjNzU4IFx1YjA1ZFx1YzVkMFx1YzExYyBcdWFjNzBcdWIzMDBcdWQ1NWMgXHVhZTA4XHVhZDM0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWI0NThcdWM3NzRcdWMxMWMgXHViNGU0XHVhY2UwIFx1YjA5OFx1YWMwMFx1YWUzMFx1YzVkNCBcdWFlMDhcdWFkMzRcdWIyOTQgXHViMTA4XHViYjM0IFx1YWM3MFx1YjMwMFx1ZDU1OFx1YWNlMCBcdWJiMzRcdWFjNzBcdWM2ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1YzZcdWM3NDRcdWFlNGMgXHVhY2UwXHViYmZjXHVkNTU4XHViMzU4IFx1YzkxMSwgXHVjOWMwXHVkNjA0XHVjNzc0XHVhYzAwIFx1YWUwOFx1YWQzNFx1YzVkMCBcdWMyMmJcdWM3OTAgblx1Yzc3NCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWMyMWNcdWFjMDQgXHVjNjk0XHVjODE1XHVjNzc0IFx1YjA5OFx1ZDBjMFx1YjA5OCBcdWI5ZDBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNjk0XHVjODE1IDogXHVjNzc0IFx1YWUwOFx1YWQzNFx1YjI5NCBcdWJiMzRcdWFjNzBcdWM2Y2MuIFx1Yzc3NFx1YWM3NCBcdWJiMzRcdWI4MjQgMjxzdXA+bjxcL3N1cD4gXHVkM2E4XHVkMWEwXHVhZGY4XHViN2E4XHVjNzc4XHVhYzc4LiBcdWFjOGNcdWIyZTRcdWFjMDAgblx1Yzc0MCA2Mlx1YWU0Y1x1YzljMCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWQ2Yy48XC9saT5cclxuXHQ8bGk+XHVhYzE1XHVjMGIwIDogXHVjNWI0LCBcdWFkZjhcdWI4MDdcdWIyZTRcdWJhNzQgXHVjNmI0XHVjNzc0IFx1Yzg4Ylx1Yzc0MFx1YWM3OFx1YzY5NCEgXHVjOWMwXHVkNjA0XHVjNzc0IFx1YWMwMFx1YmMyOVx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggYSBcdWQzYThcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHViMmY0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzgxYyBcdWFjMDBcdWJjMjlcdWM3NDAgYiBcdWQzYThcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHViMmY0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVjNzc0IFx1YjU0YyBhICsgYiA9IDI8c3VwPm48XC9zdXA+XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjJjOFx1YWU0Y1x1YzY5NCE8XC9saT5cclxuXHQ8bGk+XHVjOWMwXHVkNjA0IDogXHVhZGZjXHViMzcwIFx1YzViNFx1YjViYlx1YWM4YyBcdWFlMDhcdWFkMzRcdWI5N2MgXHVjNzkwXHViOTc0XHVjOWMwPzxcL2xpPlxyXG5cdDxsaT5cdWM2OTRcdWM4MTUgOiBcdWIwYjQgXHViOWM4XHViYzk1XHVjNzNjXHViODVjIFx1YzViNFx1YjVhNCBcdWJiM2NcdWFjNzRcdWM3NzRcdWI0ZTAgXHVjODE1XHVkNjU1XHVkNzg4IFx1YmMxOFx1ZDFhMFx1YjljOVx1Yzc0NCBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YzViNC4gXHVhZGZjXHViMzcwIFx1YjA5YyBcdWI5YzhcdWJjOTVcdWM3NDQgXHVkNTU4XHViOGU4XHVjNWQwIFx1ZDU1YyBcdWJjODhcdWJjMTZcdWM1ZDAgXHViYWJiIFx1YzRmMFx1YjI5NFx1YjM3MC4uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzE1XHVjMGIwXHVjNzc0XHVjNjQwIFx1YzljMFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWJhNzBcdWNlNjAgXHVkNmM0LCBcdWFlMDhcdWFkMzRcdWI5N2MgXHViYWE4XHViNDUwIFx1YjA5OFx1YjIyMCBcdWFjMTZcdWFjZTAgXHViM2Q5XHVhZDc0XHVjNzQ0IFx1YjA5OFx1YzEzMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgXHVhYzE1XHVjMGIwXHVjNzc0XHVjNjQwIFx1YzljMFx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWIzZDlcdWFkNzRcdWM3NDQgXHViMDk4XHVjMTIwIFx1YWM3NCBcdWIzZDlcdWFkNzRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjI4IFx1YjRhNCBcdWJhNzBcdWNlNjAgXHViNGE0XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggdCAmbGU7IDEwMDAgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwIHRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWM4MTVcdWMyMTggbiwgYSwgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPiggYSwgYiAmZ2U7IDEsIGEgKyBiID0gMjxcL3NwYW4+PHN1cCBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+bjxcL3N1cD48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+LCAxICZsZTsgbiAmbGU7IDYyLik8XC9zcGFuPjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzE1XHVjMGIwXHVjNzc0XHVjNjQwIFx1YzljMFx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWIzZDlcdWFkNzRcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWI1YTBcdWIwYWNcdWM3NDQgXHViNTRjIFx1YmE3MFx1Y2U2MFx1Yzc3NCBcdWM5YzBcdWIwYWNcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjc1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR29sZCBSdXNoIiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSBhbmQgQm9iIGFyZSBvbiBhbiBhZHZlbnR1cmUgdHJpcC4gRGVlcCBpbiB0aGUgd29vZHMgdGhleSBkaXNjb3ZlciBhIG15c3RlcmlvdXMgZGVlcCBjYXZlIHdoaWNoIHRoZXkgZW50ZXIgZmx1dHRlcmluZ2x5LiBUaGV5IGZpbmQgYW4gb2xkIGNvbnNvbGUgd2l0aCBhIGdpYW50IGJhciBvZiBnb2xkIGluIGl0LiBPbiB0aGUgYmFyLCB0aGVyZSBpcyBhIG51bWJlciBuLiBCb3RoIHRyaWVkIHRvIGNhcnJ5IHRoZSBnb2xkIG91dCB0aGUgY2F2ZSwgYnV0IGl0IHdhcyBzdGlsbCB0byBoZWF2eSBmb3Igb25lIG9mIHRoZW0uPFwvcD5cclxuXHJcbjxwPlN1ZGRlbmx5IGEgbGl0dGxlIGZhaXJ5IGFwcGVhcnMgaW4gdGhlIGNvcm5lciBvZiB0aGUgY2F2ZSBhbmQgYXBwcm9hY2hlcyBBbGljZSBhbmQgQm9iOiAmbGRxdW87VGhpcyBnb2xkIGlzIGhlYXZ5LiBJdCB3ZWlnaHRzIDI8c3VwPm48XC9zdXA+IGZlbXRvLWdyYW1zICgxMDxzdXA+LTE1PFwvc3VwPikgYW5kIG4gY2FuIHJlYWNoIDYyLiZyZHF1bzs8XC9wPlxyXG5cclxuPHA+Qm9iIGFuc3dlcmVkOiAmbGRxdW87V2hhdCBsdWNrISBBbGljZSZyc3F1bztzIGtuYXBzYWNrIGNhbiBjYXJyeSB1cCB0byBhIGZlbXRvLWdyYW1zIGFuZCBtaW5lIGIgZmVtdG8tZ3JhbXMgd2l0aCBhICsgYiA9IDI8c3VwPm48XC9zdXA+LiZyZHF1bzsgQWxpY2UgaW50ZXJqZWN0ZWQ6ICZsZHF1bztCdXQgaG93IGNhbiB3ZSBkaXZpZGUgdGhlIGdvbGQ/JnJkcXVvOzxcL3A+XHJcblxyXG48cD5GYWlyeTogJmxkcXVvO0kgY2FuIGhlbHAgeW91IHdpdGggYSBzcGVsbCB0aGF0IGNhbiBidXJzdCBvbmUgcGllY2Ugb2YgZ29sZCBpbnRvIHR3byBlcXVhbGx5IHdlaWdodGVkIG9uZXMuIEJ1dCBmb3IgZWFjaCBzaW5nbGUgc3BlbGwsIHRoZSBjYXZlIHdpbGwgYmUgbG9ja2VkIG9uZSBhZGRpdGlvbmFsIGRheS4mcmRxdW87PFwvcD5cclxuXHJcbjxwPkFsaWNlIGNvbnN1bHRzIHdpdGggQm9iIHRvIHVzZSB0aGUgaGVscCBvZiB0aGUgZmFpcnkgYW5kIHRha2UgYWxsIG9mIHRoZSBnb2xkLiBIb3cgbG9uZyB3aWxsIHRoZXkgYmUgdHJhcHBlZCBpZiB0aGV5IGFyZSBjbGV2ZXI/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggdGhlIG51bWJlciB0ICZsZTsgMTAwMCBvZiB0ZXN0IGNhc2VzLiBUaGVuIHQgbGluZXMgZm9sbG93LCBlYWNoIGRlc2NyaWJpbmcgYSBzaW5nbGUgdGVzdCBjYXNlIGNvbnNpc3Rpbmcgb2YgdGhyZWUgbnVtYmVycyBuLCBhIGFuZCBiIHdpdGggYSwgYiAmZ2U7IDEsIGEgKyBiID0gMjxzdXA+bjxcL3N1cD4sIGFuZCAxICZsZTsgbiAmbGU7IDYyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBmb3IgZXZlcnkgdGVzdCBjYXNlIHdpdGggdGhlIG1pbmltYWwgbnVtYmVyIG9mIGRheXMgdGhhdCBBbGljZSBhbmQgQm9iIGFyZSBsb2NrZWQgaW4gdGhlIGNhdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d