Anubhav has a crush on Anu. Therefore he likes the letters A,N and U the most.
He likes those strings which consists of only A N U
According to him, the strings containing A,N and U only are "LOVABLE" If they contain either of these patterns:
1) ANU
2) AUN
3) NAU
4) NUA
5) UAN
6) UNA
He asks you to find out how many LOVABLE strings are there of length N.
Note: Assume all strings are made of A,N,U. Consider all other alphabets as non-existent.
Input format: First line contains T the number of test cases. Next T lines contain a single integer N, denoting the length of string
Output format: Output the count of LOVABLE strings of length N in a single line for each test case
Constraints:
1<= T <= 30
1<= N <= 30
Solution :
The dynamic programming solution will be uploaded soon, Stay tuned.
Comments
Post a Comment