You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在数学王国里，有一类特殊的数字，它们被亲切地称为“自和数”。 相传，古时候的数学家发现，如果一个数能被它自身的各位数字之和整除，那么这个数就拥有一种内在的和谐之美。这种数既能体现数字的组成，又能保持与自身的完美平衡，因此被赋予了“自和”之名。 如今，你的任务是帮助数学家们统计在某个区间内，到底有多少个这样的自和数。

题目描述

如果一个正整数能够被它的各位数字之和整除，则称这个数为“自和数”。 例如，$18$ 的各位数字之和为 $1+8=9$，$18$ 能被 $9$ 整除，因此$18$ 是一个自和数。

给定正整数 $L$ 和 $R$，请统计闭区间 $[L, R]$ 内自和数的个数。

输入格式

第一行一个正整数$T$，表示$T$个询问，接下来$T$行每行包含两个正整数 $L$ 和 $R$。

输出格式

对于每个询问，输出一行一个正整数，表示该区间内自和数的个数。

输入输出样例 #1

输入 #1

1
1 100

输出 #1

33

说明/提示

数据范围

• $1 \le L, R < 2^{31}$
• 单个测试点内的数据组数不超过 $3000$

说明

• 由于数据范围较大，直接枚举会超时，请设计高效的算法。