1122 - Digit Count 

Given a set of digits S, and an integer n, you have to find how many n-digit integers are there, which contain digits that belong to S and the difference between any two adjacent digits is not more than two.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case contains two integers, m (1 ≤ m < 10) and n (1 ≤ n ≤ 10). The next line will contain m integers (from 1 to 9) separated by spaces. These integers form the set S as described above. These integers will be distinct and given in ascending order.

Output

For each case, print the case number and the number of valid n-digit integers in a single line.

Sample Input	Output for Sample Input
3 3 2 1 3 6 3 2 1 2 3 3 3 1 4 6	Case 1: 5 Case 2: 9 Case 3: 9

Note

For the first case the valid integers are

11

---------------------------------------------editorial----------------------------------------------------------

normal recursive dp

-----------------------------------------code--------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli dp[20][20];

 int m,n;

 int has[11];

lli solve(int idx,int last)

 {

   if(idx==n) return 1;

   else if(dp[idx][last]!=-1)

   return dp[idx][last];

   else

   {

    lli ret=0;

    for(int i=0;i<=9;i++)

     {

       if(abs(last-i)<=2 && has[i])

         ret+=solve(idx+1,i);

   }

   dp[idx][last]=ret;

   return ret;

  }

 }

int main()

 {

  int t;

   cin>>t;

   int cas=1;

   while(t--)

    {

     memset(has,0,sizeof has);

      

        cin>>m>>n;

        for(int i=0;i<m;i++)

            {

           int a;

            cin>>a;

            has[a]++;

   }

   lli ans=0;

   for(int i=0;i<=9;i++)

   {

        memset(dp,-1,sizeof dp);

        if(has[i])

        {

        //  cout<<"start with "<<i<<endl;

         ans+=solve(1,i);

   }

   

   }

    cout<<"Case "<<cas++<<": "<<ans<<endl;

    

   }

 }