Adjacent Bit Pair Count

Let S = s1, s2, ..., sn be a sequence of length n containing only 0s and 1s. Define the adjacent bit pair count of S as the following sum.

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

Each term contributes 1 exactly when two neighboring bits are both 1, so this value is the number of adjacent 11 pairs in the sequence. The value is 3 for 011101101, 4 for 111101101, and 0 for 010101010.

Given the length n and a target value k, count how many binary sequences have adjacent bit pair count exactly k.

When n = 5 and k = 2, the valid sequences are 11100, 01110, 00111, 10111, 11101, and 11011, for a total of 6.

The first line contains the number of test cases T (1 <= T <= 1,000).

Each test case consists of one line with two integers n and k. Here n is between 1 and 100 inclusive, and k is between 0 and 100 inclusive.

For each test case, print one line containing the number of binary sequences of length n whose adjacent bit pair count is k.

Every required answer is at most 2,147,483,647.