로또

면접 대비

시간 제한1초메모리 제한128 MB

요약

1부터 m까지 중 n개를 골라 정렬했을 때 각 수가 앞 수의 두 배 이상이 되는 조합의 개수를 구합니다.

문제

선영이는 매주 로또에 큰돈을 쓴다. 이 로또는 1부터 m까지의 정수 중 서로 다른 n개를 고르는 방식이다.

선영이는 고른 수를 작은 것부터 나열했을 때, 두 번째 수부터는 바로 앞의 수의 2배 이상이 되도록만 고른다. n = 4, m = 10일 때 조건을 만족하는 방법은 4가지이다.

선영이는 가능한 각 방법마다 로또를 정확히 한 장씩 산다. n과 m이 주어질 때, 선영이가 사는 로또의 장수를 구하라.

첫째 줄에 테스트 케이스 수 T가 주어진다.

이후 각 테스트 케이스마다 정수 n과 m이 한 줄에 주어진다.

각 테스트 케이스마다 선영이가 사는 로또의 장수를 한 줄에 하나씩 출력한다.