시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 732 139 110 22.312%

문제

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다.

이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 수를 고를 때 각 숫자는 이전에 고른 수보다 적어도 2배가 되도록 고르기 때문이다.

예를 들어, n=4, m=10일 때, 선영이는 다음과 같이 고를 수 있다.

1 2 4 8

1 2 4 9

1 2 4 10

1 2 5 10

따라서 선영이는 로또를 4개 산다. 

선영이는 돈이 엄청나게 많기 때문에, 수를 고르는 방법의 수 만큼 로또를 구매하며, 같은 방법으로 2장이상 구매하지 않는다.

n과 m이 주어졌을 때, 선영이가 구매하는 로또의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 n과 m으로 이루어져 있다. 1<=n<=10, 1<=m<=2,000, n<=m

출력

각 테스트 케이스에 대해 선영이가 로또를 몇 개나 구매하는지 출력한다.

예제 입력 1

1
4 10

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjI3NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM4ZmMgXHVjNWM0XHVjY2FkXHViMDljIFx1YjNjOFx1Yzc0NCBcdWI4NWNcdWI2MTBcdWM1ZDAgXHVkMjJjXHVjNzkwXHVkNTVjXHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yjg1Y1x1YjYxMFx1YjI5NCAxXHViZDgwXHVkMTMwIG1cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwIFx1YzkxMVx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5NzRcdWIyOTQgXHViODVjXHViNjEwXHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM1ZjRcdWMyZWNcdWQ3ODggXHViODVjXHViNjEwXHViOTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVjNTQ0XHVjOWMxXHVhZTRjXHVjOWMwIFx1ZDU1YyBcdWJjODhcdWIzYzQgXHViMmY5XHVjY2E4XHViNDE4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVjMjE4XHViOTdjIFx1YWNlMFx1Yjk3YyBcdWI1NGMgXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVhY2UwXHViOTc4IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YmMzMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVhY2UwXHViOTc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgbj00LCBtPTEwXHVjNzdjIFx1YjU0YywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0MSAyIDQgODxcL3A+XHJcbjxwPlxyXG5cdDEgMiA0IDk8XC9wPlxyXG48cD5cclxuXHQxIDIgNCAxMDxcL3A+XHJcbjxwPlxyXG5cdDEgMiA1IDEwPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViODVjXHViNjEwXHViOTdjIDRcdWFjMWMgXHVjMGIwXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M4XHVjNzc0IFx1YzVjNFx1Y2NhZFx1YjA5OFx1YWM4YyBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMTggXHViOWNjXHVkMDdjIFx1Yjg1Y1x1YjYxMFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWJhNzAsIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgMlx1YzdhNVx1Yzc3NFx1YzBjMSBcdWFkNmNcdWI5ZTRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjI5NCBcdWI4NWNcdWI2MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgblx1YWNmYyBtXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIDEmbHQ7PW4mbHQ7PTEwLCAxJmx0Oz1tJmx0Oz0yLDAwMCwgbiZsdDs9bTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViODVjXHViNjEwXHViOTdjIFx1YmE4NyBcdWFjMWNcdWIwOTggXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGVubnlcdTIwMTlzIEx1Y2t5IExvdHRvIExpc3RzIiwiZGVzY3JpcHRpb24iOiI8cD5Mb3R0byBpcyBhIGxvdHRlcnksIHR5cGljYWxseSB3aXRoIGFuIGFjY3VtdWxhdGluZyBqYWNrcG90LCBpbiB3aGljaCBwYXJ0aWNpcGFudHMgcGxheSBudW1iZXJzIG9mIHRoZWlyIGNob2ljZSBpbiBhIHJhbmRvbSBkcmF3aW5nLiBMZW5ueSBsaWtlcyB0byBwbGF5IHRoZSBsb3R0byBpbiBMaW5jb2xuIGNvdW50eSBMb3Vpc2lhbmEuIEluIHRoZSBnYW1lLCBoZSBwaWNrcyBhIGxpc3Qgb2Ygbm51bWJlcnMgaW4gdGhlIHJhbmdlIGZyb20gMSB0byBtLiBJZiBoaXMgbGlzdCBtYXRjaGVzIHRoZSBkcmF3biBsaXN0LCBoZSB3aW5zIHRoZSBiaWcgcHJpemUsIGEgbGlmZXRpbWUgc3VwcGx5IG9mIGxhcmdlIGxlbW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGVubnkgaGFzIGEgc2NoZW1lIHRoYXQgaGUgdGhpbmtzIGlzIGxpa2VseSB0byBiZSBsdWNreS4gSGUgbGlrZXMgdG8gY2hvb3NlIGhpcyBsaXN0IHNvIHRoYXQgZWFjaCBudW1iZXIgaW4gaXQgaXMgYXQgbGVhc3QgdHdpY2UgYXMgbGFyZ2UgYXMgdGhlIG9uZSBiZWZvcmUgaXQuIFNvLCBmb3IgZXhhbXBsZSwgaWYgbiA9IDQgYW5kIG0gPSAxMCwgdGhlbiB0aGUgcG9zc2libGUgbHVja3kgbGlzdHMgTGVubnkgY291bGQgbGlrZSBhcmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbjEgMiA0IDhcclxuMSAyIDQgOVxyXG4xIDIgNCAxMFxyXG4xIDIgNSAxMDxcL3ByZT5cclxuXHJcbjxwPlRodXMgTGVubnkgaGFzIDQgbGlzdHMgdG8gY2hvb3NlIGZyb20uJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgam9iLCBnaXZlbiBuIGFuZCBtLCBpcyB0byBjb3VudCBob3cgbWFueSBsdWNreSBsaXN0cyBMZW5ueSBoYXMgdG8gY2hvb3NlIGZyb20uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBub24tbmVnYXRpdmUgaW50ZWdlciwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdG8gZm9sbG93LiBBbGwgZGF0YSBzZXRzIHNob3VsZCBiZSBoYW5kbGVkIGlkZW50aWNhbGx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lcywgb25lIHBlciBkYXRhIHNldCwgY29udGFpbiB0d28gaW50ZWdlcnMsIG4gYW5kIG0uIFlvdSBhcmUgZ3VhcmFudGVlZCB0aGF0IDEgJmx0Oz0gbiAmbHQ7PSAxMCBhbmQgMSAmbHQ7PSBtICZsdDs9IDIwMDAgYW5kIG4gJmx0Oz0gbS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgcHJpbnQgYSBsaW5lIGxpa2UgdGhlIGZvbGxvd2luZzombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuRGF0YSBzZXQgaTogbiBtIG51bWJlcjxcL3ByZT5cclxuXHJcbjxwPndoZXJlIGkgaXMgdGhlIGRhdGEgc2V0IG51bWJlciAoYmVnaW5uaW5nIHdpdGggMSksIGFuZCBudW1iZXJpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgbHVja3kgbGlzdHMgY29ycmVzcG9uZGluZyB0byB0aGUgcHJvdmlkZWQgdmFsdWVzIG9mIG4gYW5kIG0uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d