If we define , do you know what function  means?

Actually,  calculates the total number of enclosed areas produced by each digit in . The following table shows the number of enclosed areas produced by each digit:

For example, , and .

We now define a recursive function  by the following equations:

For example, , and .

Given two integers  and , please calculate the value of .

Input

There are multiple test cases. The first line of the input contains an integer  (about ), indicating the number of test cases. For each test case:

The first and only line contains two integers and  (). Positive integers are given without leading zeros, and zero is given with exactly one '0'.

<h4< dd="">Output

For each test case output one line containing one integer, indicating the value of .

<h4< dd="">Sample Input

6
123456789 1
888888888 1
888888888 2
888888888 999999999
98640 12345
1000000000 0

<h4< dd="">Sample Output

5
18
2
0
0
1000000000

这道题看第一眼，很容易想到暴力，然后就零分了。

不过仔细观察

观察一下0-9对应的值，很容易发现他们最后都指向了0，1

其余的数同理，最后都会指向1.0；

而0，1的值又是相互对应的。

我们就可以优化了--------------------

链接：不知道

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n;
 5 const long long   maxn=1e6;
 6 int head;
 7 int x;
 8 int k;
 9 int deal1(int  x);
10 long long  f[maxn]={1,0,0,0,1,0,1,0,2,1};
11 void deal(int k,int x){
12     while(x>=2&&k){
13 //        cout<<"d"<<x<<endl;
14         x=deal1(x);
15         k--;
16     }
17 //    cout<<x<<endl
18     if(!k)
19     {
20         cout<<x<<endl;
21         return ;
22     }
23     if(k%2)
24     printf("%dn",(!x));
25     else
26     printf("%dn",x);
27     return ;
28 }
29 
30 int deal1(int  x){
31         int  ans=0;
32         long long now;
33         while(x){
34             now=x%10;
35             x/=10;
36             ans+=f[now];
37             //cout<<now<<"dfsd"<<endl;
38         }
39     return ans;
40 }
41 int main(){
42     scanf("%d",&n);
43     for(int i=1;i<=n;++i){
44         scanf("%d%d",&x,&k);
45         if(k==0){
46             printf("%dn",x);    
47         }
48         else
49         deal(k,x);
50     }
51     return 0;
52 } 

Ac