//{ Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GfG
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
Solution ob = new Solution();
System.out.println(ob.getCount(n));
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution
{
public long getCount(int n)
{
/*Q51 dp playlist ,
*/
long ans = 0;
//make dp , keep no.of presses on rows and keypad nums on cols
long[][] dp = new long[n+1][10];
//store the info of which keypads can be pressed for which keypads
int[][] data = {
{0,8},
{1,2,4},
{1,2,3,5},
{3,2,6},
{4,1,5,7},
{4,5,6,2,8},
{3,6,9,5},
{4,7,8},
{5,7,8,9,0},
{6,8,9}
};
//i==0 will be all 0 by default
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j <= 9 ; j++){
//if 1st row only 1 number can be created with 1 press
if(i==1)
dp[i][j] = 1;
/* if more than 1 press add all the (i-1)th press numbers generated
for all numbers which can be pressed after current key stored in data[]
*/
else{
for(int prev : data[j])
dp[i][j] += dp[i-1][prev];
}
}
}
//total numbers can be created with n presses will be sum of last row
for(int j = 0; j <= 9 ; j++)
ans += dp[n][j];
return ans;
}
}
Comments