Mobile Keypad Problem
Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and #).
Given a number N, find out the number of possible numbers of given length.
The problem basically needs a little bit of knowledge of mobile keypad configuration, you are required to count the different numbers that you can form with the help of certain digit that is equal to a given size, eg let N=5 then one possible number is 12345 since it has 5 digits in it. Hence with a certain algorithm, you need to develop a program that prints the total possible count of such numbers.
First line consists of T test case. Only line of the test case consists of N.
Print the possible numbers of given length.