Adjacent Bit Counts#2445
For a string of bits x_1, x_2, x_3, \ldots, x_n, the adjacent bit count of the string () is given by
which counts the number of times a bit is adjacent to another bit. For example:
\operatorname{AdjBC}(011101101) = 3,\ \operatorname{AdjBC}(111101101) = 4,\ \operatorname{AdjBC}(010101010) = 0
Write a program which takes as input integers and and returns the number of bit strings of bits (out of 2^n) that satisfy \operatorname{AdjBC}(x) = k. For example, for -bit strings, there are ways of getting \operatorname{AdjBC}(x) = 2:
\mathbf{11100},\ \mathbf{01110},\ \mathbf{00111},\ \mathbf{10111},\ \mathbf{11101},\ \mathbf{11011}
The first line of input contains a single integer (1 \leq P \leq 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number () of bits in the bit strings, followed by a single space, followed by a decimal integer () giving the desired adjacent bit count. The number of bits () will not be greater than and the parameters and will be chosen so that the result will fit in a signed -bit integer.
For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of -bit strings with adjacent bit count equal to .
Example 1