Can somebody explain me this question?

#1

CLASS ASSIGNMENT
In a mathematics class, Teacher ask Alice to find the number of all n digit distinct integers which is formed by the two distinct digits ai and bi but there is a rule to form n digit integer.

Rule: She has to form n digit integer by using two digits ai and bi without consecutive bi.

Alice is very weak in maths section. Help her to find the number of such n digit integers.

Input Format:
The first line contains T, the number of test cases. Further T lines contains the value n which is the number of digit in the integer.

Constraints:
1<=T<=40 1<=n<44

Output Format
For each test case print the number of such n digit integer.

Sample Input
3
1
2
3
Sample Output
#1 : 2
#2 : 3
#3 : 5

#2

It’s quite simple actually. Just think of this question as counting all sequences of length n that can be formed using 2 different characters: a and b . Just one condition: do not count all those sequences that have atleast a pair of consecutive b’s in them. For e…g, for n = 7, such as sequence as “abaabaa” is valid and should be counted while “abbaaba” shouldn’t be counted as it contains a pair of consecutive b’s . This can be solved using dynamic programming. Just consider the 2 states of DP to be the ‘the number of ways to make sequences of length i such that it ends in a’ and ‘no. of ways to make sequences of length i such that it ends in b’.

#3

thnq for the explanation