# 山东省第八届 ACM 省赛 Quadrat （找规律）

## Description

It is well-known that for any n there are exactly four n-digit numbers (including ones with leading zeros) that are self-squares: the last n digits of the square of such number are equal to the number itself. These four numbers are always suffixes of these four infinite sequences:

...0000000000

...0000000001

...8212890625

...1787109376

For example, =87909376, which ends with 09376.

You are required to count the numbers that are almost self-squares: such that each of the last n digits of their square is at most d away from the corresponding digit of the number itself. Note that we consider digits 0 and 9 to be adjacent, so for example digits that are at most 3 away from digit 8 are 5, 6, 7, 8, 9, 0 and 1.

## Input

The first line contains the number of test cases t,1≤t≤72. Each of the next t lines contains one test case: two numbers n(1≤n≤ 18) and d(0≤ d≤3).

## Output

For each test case, output the number of almost self-squares with length n and the (circular) distance in each digit from the square at most d in a line by itself.

## Example Input

2
5 0
2 1


## Example Output

4
12


## Hint

In the second case, number 12's almost self-squares are: 00, 01, 10, 11, 15, 25, 35, 66, 76, 86, 90, 91

## 思路

1:      4 4 8 8
2:      4 12 40 56
3:      4 36 200 392
4:      4 108 1000 2744


## AC 代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#include<queue>
#include<map>
const int mod = 1e9+7;
typedef long long LL;

LL dp[20][4];
void init()
{
dp[1][0]=dp[1][1]=4;
dp[1][2]=dp[1][3]=8;
for(int i=2; i<=18; i++)
for(int j=0; j<4; j++)
dp[i][j]=dp[i-1][j]*(2*j+1);
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
int n,k;
cin>>n>>k;
cout<<dp[n][k]<<endl;
}
return 0;
}