인접한 비트 쌍의 개수

0과 1로만 이루어진 길이 n의 수열 S = s1, s2, ..., sn이 있다. 다음 합을 S의 인접한 비트 쌍의 개수라고 하자.

s1 * s2 + s2 * s3 + s3 * s4 + ... + s(n-1) * sn

각 항은 이웃한 두 비트가 모두 1일 때만 1이 되므로, 이 값은 수열 안에 서로 붙어 있는 11 쌍이 몇 개인지를 나타낸다. 수열 011101101의 값은 3, 111101101의 값은 4, 010101010의 값은 0이다.

수열의 길이 n과 목표값 k가 주어질 때, 인접한 비트 쌍의 개수가 정확히 k인 0-1 수열의 개수를 구하라.

n = 5, k = 2일 때 조건을 만족하는 수열은 11100, 01110, 00111, 10111, 11101, 11011로 모두 6개이다.

첫째 줄에 테스트 케이스의 수 T (1 <= T <= 1,000)가 주어진다.

각 테스트 케이스는 한 줄에 두 정수 n과 k로 주어진다. n은 1 이상 100 이하이고, k는 0 이상 100 이하이다.

각 테스트 케이스마다 길이가 n이고 인접한 비트 쌍의 개수가 k인 0-1 수열의 개수를 한 줄에 하나씩 출력한다.

출력해야 하는 값은 2,147,483,647 이하이다.