Quadrat

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大学生程序设计竞赛(感谢青岛科技大学)