PLEASE WRITE COMMENTS AND PSEUDO CODE WITH THE CODE!! Adjacent Bit Number Problem 1: Introduction Problem description an

[answerhappygod]

PLEASE WRITE COMMENTS AND PSEUDO CODE WITH THE
CODE!!
Adjacent Bit Number Problem
1: Introduction
Problem description and (if any) background of the
algorithms.
Description:
An n-bit 0, 1 string x =
x1x2 …xn, the number of
adjacent bits is determined by the function: fun (x) =
x1*x2+x2*x3+…
xn-1xn is calculated, which calculates
the number of occurrences of two adjacent 1s. For example:
fun(011101101)=3
fun(111101101)=4
Please write a program, taking n and p as inputs, and find the
number of x with length n satisfying fun (x)=p. For example, the
result of n=5 and p=2 is 6, that is, x has 11100, 01110, 00111,
10111, 11101 and 11011.
Input:
The first line is a positive integer k(1k10), indicating the
number of test cases, followed by k test cases, one line for each
test case, including n(1n100) and p(1n100).
Output:
For each test case, an integer is output to represent the number
of 0 and 1 strings with the number of adjacent bits equal to p.
Sample Input
2
5 2
20 8
Sample Output
6
63426