시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 794 155 122 23.150%

문제

선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 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
W3sicHJvYmxlbV9pZCI6IjI3NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM4ZmMgXHVjNWM0XHVjY2FkXHViMDljIFx1YjNjOFx1Yzc0NCBcdWI4NWNcdWI2MTBcdWM1ZDAgXHVkMjJjXHVjNzkwXHVkNTVjXHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVkNTU4XHViMjk0IFx1Yjg1Y1x1YjYxMFx1YjI5NCAxXHViZDgwXHVkMTMwIG1cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwIFx1YzkxMVx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5NzRcdWIyOTQgXHViODVjXHViNjEwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjNWY0XHVjMmVjXHVkNzg4IFx1Yjg1Y1x1YjYxMFx1Yjk3YyBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YzU0NFx1YzljMVx1YWU0Y1x1YzljMCBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YjJmOVx1Y2NhOFx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNzc0XHVjNzIwXHViMjk0IFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5N2MgXHViNTRjIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjNzc0XHVjODA0XHVjNWQwIFx1YWNlMFx1Yjk3OCBcdWMyMThcdWJjZjRcdWIyZTQgXHVjODAxXHVjNWI0XHViM2M0IDJcdWJjMzBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YWNlMFx1Yjk3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIG49NCwgbT0xMFx1Yzc3YyBcdWI1NGMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgMiA0IDg8XC9saT5cclxuXHQ8bGk+MSAyIDQgOTxcL2xpPlxyXG5cdDxsaT4xIDIgNCAxMDxcL2xpPlxyXG5cdDxsaT4xIDIgNSAxMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViODVjXHViNjEwXHViOTdjIDRcdWFjMWMgXHVjMGIwXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M4XHVjNzc0IFx1YzVjNFx1Y2NhZFx1YjA5OFx1YWM4YyBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMTggXHViOWNjXHVkMDdjIFx1Yjg1Y1x1YjYxMFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWJhNzAsIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgMlx1YzdhNVx1Yzc3NFx1YzBjMSBcdWFkNmNcdWI5ZTRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5uXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjI5NCBcdWI4NWNcdWI2MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgblx1YWNmYyBtXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWI4NWNcdWI2MTBcdWI5N2MgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBtICZsZTsgMiwwMDA8XC9saT5cclxuXHQ8bGk+biAmbGU7IG08XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI3NTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMZW5ueVx1MjAxOXMgTHVja3kgTG90dG8gTGlzdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkxvdHRvIGlzIGEgbG90dGVyeSwgdHlwaWNhbGx5IHdpdGggYW4gYWNjdW11bGF0aW5nIGphY2twb3QsIGluIHdoaWNoIHBhcnRpY2lwYW50cyBwbGF5IG51bWJlcnMgb2YgdGhlaXIgY2hvaWNlIGluIGEgcmFuZG9tIGRyYXdpbmcuIExlbm55IGxpa2VzIHRvIHBsYXkgdGhlIGxvdHRvIGluIExpbmNvbG4gY291bnR5IExvdWlzaWFuYS4gSW4gdGhlIGdhbWUsIGhlIHBpY2tzIGEgbGlzdCBvZiBubnVtYmVycyBpbiB0aGUgcmFuZ2UgZnJvbSAxIHRvIG0uIElmIGhpcyBsaXN0IG1hdGNoZXMgdGhlIGRyYXduIGxpc3QsIGhlIHdpbnMgdGhlIGJpZyBwcml6ZSwgYSBsaWZldGltZSBzdXBwbHkgb2YgbGFyZ2UgbGVtb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZW5ueSBoYXMgYSBzY2hlbWUgdGhhdCBoZSB0aGlua3MgaXMgbGlrZWx5IHRvIGJlIGx1Y2t5LiBIZSBsaWtlcyB0byBjaG9vc2UgaGlzIGxpc3Qgc28gdGhhdCBlYWNoIG51bWJlciBpbiBpdCBpcyBhdCBsZWFzdCB0d2ljZSBhcyBsYXJnZSBhcyB0aGUgb25lIGJlZm9yZSBpdC4gU28sIGZvciBleGFtcGxlLCBpZiBuID0gNCBhbmQgbSA9IDEwLCB0aGVuIHRoZSBwb3NzaWJsZSBsdWNreSBsaXN0cyBMZW5ueSBjb3VsZCBsaWtlIGFyZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuMSAyIDQgOFxyXG4xIDIgNCA5XHJcbjEgMiA0IDEwXHJcbjEgMiA1IDEwPFwvcHJlPlxyXG5cclxuPHA+VGh1cyBMZW5ueSBoYXMgNCBsaXN0cyB0byBjaG9vc2UgZnJvbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91ciBqb2IsIGdpdmVuIG4gYW5kIG0sIGlzIHRvIGNvdW50IGhvdyBtYW55IGx1Y2t5IGxpc3RzIExlbm55IGhhcyB0byBjaG9vc2UgZnJvbS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgc2luZ2xlIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0byBmb2xsb3cuIEFsbCBkYXRhIHNldHMgc2hvdWxkIGJlIGhhbmRsZWQgaWRlbnRpY2FsbHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmVzLCBvbmUgcGVyIGRhdGEgc2V0LCBjb250YWluIHR3byBpbnRlZ2VycywgbiBhbmQgbS4gWW91IGFyZSBndWFyYW50ZWVkIHRoYXQgMSAmbHQ7PSBuICZsdDs9IDEwIGFuZCAxICZsdDs9IG0gJmx0Oz0gMjAwMCBhbmQgbiAmbHQ7PSBtLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBwcmludCBhIGxpbmUgbGlrZSB0aGUgZm9sbG93aW5nOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5EYXRhIHNldCBpOiBuIG0gbnVtYmVyPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgaSBpcyB0aGUgZGF0YSBzZXQgbnVtYmVyIChiZWdpbm5pbmcgd2l0aCAxKSwgYW5kIG51bWJlcmlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBsdWNreSBsaXN0cyBjb3JyZXNwb25kaW5nIHRvIHRoZSBwcm92aWRlZCB2YWx1ZXMgb2YgbiBhbmQgbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=