### Quadrat

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