시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 542 222 191 43.409%

문제

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

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

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

방법이 없을까 고민하던 중, 지현이가 금괴에 숫자 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+XHVhYzE1XHVjMGIwIDogXHVjNWI0LCBcdWFkZjhcdWI4MDdcdWIyZTRcdWJhNzQgXHVjNmI0XHVjNzc0IFx1Yzg4Ylx1Yzc0MFx1YWM3OFx1YzY5NCEgXHVjOWMwXHVkNjA0XHVjNzc0IFx1YWMwMFx1YmMyOVx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggYSBcdWQzYThcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHViMmY0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzgxYyBcdWFjMDBcdWJjMjlcdWM3NDAgYiBcdWQzYThcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHViMmY0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVjNzc0XHViNTRjIGEgKyBiID0gMjxzdXA+bjxcL3N1cD5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMmM4XHVhZTRjXHVjNjk0ITxcL2xpPlxyXG5cdDxsaT5cdWM5YzBcdWQ2MDQgOiBcdWFkZmNcdWIzNzAgXHVjNWI0XHViNWJiXHVhYzhjIFx1YWUwOFx1YWQzNFx1Yjk3YyBcdWM3OTBcdWI5NzRcdWM5YzA/PFwvbGk+XHJcblx0PGxpPlx1YzY5NFx1YzgxNSA6IFx1YjBiNCBcdWI5YzhcdWJjOTVcdWM3M2NcdWI4NWMgXHVjNWI0XHViNWE0IFx1YmIzY1x1YWM3NFx1Yzc3NFx1YjRlMCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViYzE4XHVkMWEwXHViOWM5XHVjNzQ0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNWI0LiBcdWFkZmNcdWIzNzAgXHViMDljIFx1YjljOFx1YmM5NVx1Yzc0NCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVkNTVjIFx1YmM4OFx1YmMxNlx1YzVkMCBcdWJhYmIgXHVjNGYwXHViMjk0XHViMzcwLi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjMTVcdWMwYjBcdWM3NzRcdWM2NDAgXHVjOWMwXHVkNjA0XHVjNzc0XHViMjk0IFx1YmE3MFx1Y2U2MCBcdWQ2YzQsIFx1YWUwOFx1YWQzNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViMDk4XHViMjIwIFx1YWMxNlx1YWNlMCBcdWIzZDlcdWFkNzRcdWM3NDQgXHViMDk4XHVjMTMwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YzY0MCBcdWM5YzBcdWQ2MDRcdWM3NzRcdWFjMDAgXHViM2Q5XHVhZDc0XHVjNzQ0IFx1YjA5OFx1YzEyMCBcdWFjNzQgXHViM2Q5XHVhZDc0XHVjNWQwIFx1YjRlNFx1YzViNFx1YzYyOCBcdWI0YTQgXHViYTcwXHVjZTYwIFx1YjRhNFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IHQgJmxlOyAxMDAwIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCB0XHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCwgXHVjODE1XHVjMjE4IG4sIGEsIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4oIGEsIGIgJmdlOyAxLCBhICsgYiA9IDI8XC9zcGFuPjxzdXAgc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPm48XC9zdXA+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPiwgMSAmbGU7IG4gJmxlOyA2Mi4pPFwvc3Bhbj48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YzY0MCBcdWM5YzBcdWQ2MDRcdWM3NzRcdWFjMDAgXHViM2Q5XHVhZDc0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjhcdWI5YWMgXHViNWEwXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWJhNzBcdWNlNjBcdWM3NzQgXHVjOWMwXHViMGFjXHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDI3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdvbGQgUnVzaCIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgYW5kIEJvYiBhcmUgb24gYW4gYWR2ZW50dXJlIHRyaXAuIERlZXAgaW4gdGhlIHdvb2RzIHRoZXkgZGlzY292ZXIgYSBteXN0ZXJpb3VzIGRlZXAgY2F2ZSB3aGljaCB0aGV5IGVudGVyIGZsdXR0ZXJpbmdseS4gVGhleSBmaW5kIGFuIG9sZCBjb25zb2xlIHdpdGggYSBnaWFudCBiYXIgb2YgZ29sZCBpbiBpdC4gT24gdGhlIGJhciwgdGhlcmUgaXMgYSBudW1iZXIgbi4gQm90aCB0cmllZCB0byBjYXJyeSB0aGUgZ29sZCBvdXQgdGhlIGNhdmUsIGJ1dCBpdCB3YXMgc3RpbGwgdG8gaGVhdnkgZm9yIG9uZSBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5TdWRkZW5seSBhIGxpdHRsZSBmYWlyeSBhcHBlYXJzIGluIHRoZSBjb3JuZXIgb2YgdGhlIGNhdmUgYW5kIGFwcHJvYWNoZXMgQWxpY2UgYW5kIEJvYjogJmxkcXVvO1RoaXMgZ29sZCBpcyBoZWF2eS4gSXQgd2VpZ2h0cyAyPHN1cD5uPFwvc3VwPiBmZW10by1ncmFtcyAoMTA8c3VwPi0xNTxcL3N1cD4pIGFuZCBuIGNhbiByZWFjaCA2Mi4mcmRxdW87PFwvcD5cclxuXHJcbjxwPkJvYiBhbnN3ZXJlZDogJmxkcXVvO1doYXQgbHVjayEgQWxpY2UmcnNxdW87cyBrbmFwc2FjayBjYW4gY2FycnkgdXAgdG8gYSBmZW10by1ncmFtcyBhbmQgbWluZSBiIGZlbXRvLWdyYW1zIHdpdGggYSArIGIgPSAyPHN1cD5uPFwvc3VwPi4mcmRxdW87IEFsaWNlIGludGVyamVjdGVkOiAmbGRxdW87QnV0IGhvdyBjYW4gd2UgZGl2aWRlIHRoZSBnb2xkPyZyZHF1bzs8XC9wPlxyXG5cclxuPHA+RmFpcnk6ICZsZHF1bztJIGNhbiBoZWxwIHlvdSB3aXRoIGEgc3BlbGwgdGhhdCBjYW4gYnVyc3Qgb25lIHBpZWNlIG9mIGdvbGQgaW50byB0d28gZXF1YWxseSB3ZWlnaHRlZCBvbmVzLiBCdXQgZm9yIGVhY2ggc2luZ2xlIHNwZWxsLCB0aGUgY2F2ZSB3aWxsIGJlIGxvY2tlZCBvbmUgYWRkaXRpb25hbCBkYXkuJnJkcXVvOzxcL3A+XHJcblxyXG48cD5BbGljZSBjb25zdWx0cyB3aXRoIEJvYiB0byB1c2UgdGhlIGhlbHAgb2YgdGhlIGZhaXJ5IGFuZCB0YWtlIGFsbCBvZiB0aGUgZ29sZC4gSG93IGxvbmcgd2lsbCB0aGV5IGJlIHRyYXBwZWQgaWYgdGhleSBhcmUgY2xldmVyPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIHRoZSBudW1iZXIgdCAmbGU7IDEwMDAgb2YgdGVzdCBjYXNlcy4gVGhlbiB0IGxpbmVzIGZvbGxvdywgZWFjaCBkZXNjcmliaW5nIGEgc2luZ2xlIHRlc3QgY2FzZSBjb25zaXN0aW5nIG9mIHRocmVlIG51bWJlcnMgbiwgYSBhbmQgYiB3aXRoIGEsIGIgJmdlOyAxLCBhICsgYiA9IDI8c3VwPm48XC9zdXA+LCBhbmQgMSAmbGU7IG4gJmxlOyA2Mi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgZm9yIGV2ZXJ5IHRlc3QgY2FzZSB3aXRoIHRoZSBtaW5pbWFsIG51bWJlciBvZiBkYXlzIHRoYXQgQWxpY2UgYW5kIEJvYiBhcmUgbG9ja2VkIGluIHRoZSBjYXZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==