Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem 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.

#### Sample Input

2
5 0
2 1


#### Sample 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

#### Source

“浪潮杯”山东省第八届ACM大学生程序设计竞赛（感谢青岛科技大学）