Judy Hopps , a rookie officer joined Zootopia Police Department. She was fond of working sincerely for the department. Chief Bogo told Hopps to study on “ZOTO” numbers.

A number is called "ZOTO" number if it follows the given rules:

the number does not contain any leading zero.

sum of digits is multiple of sum of distinct digits.

Nick Wilde is friend of Hopps. He asked her if she could answer the count of "ZOTO" number in the given range.

Hopps got busy in an investigation case. She wants help from you. As a programmer, you will write a bug free code of the problem for her.

Input

The first line containts T - the number of testcase (1<=T<=105).

Next T Lines contains two integer L, R(1<=L,R<=1018).

Output

Output T Lines - The numbers of “ZOTO” number in the given range.