题目描述

如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。

例如：2021 年 6 月 5 日的各位数字之和为 $2+0+2+1+6+5=16$，而 $16$ 是一个完全平方数，它是 $4$ 的平方。所以 2021 年 6 月 5 日是一个完全日期。

例如：$2021$ 年 $6$ 月 $23$ 日的各位数字之和为 $2+0+2+1+6+2+3=16$，是一个完全平方数。所以 $2021$ 年 $6$ 月 $23$ 日也是一个完全日期。

请问，从 $X$ 年 $1$ 月 $1$ 日到 $Y$ 年 $12$ 月 $31$ 日中，一共有多少个完全日期？

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 $1$ 个整数 $N$。

输出描述

对每个输入输出一个整数表示答案。

2
1 40
1987 2022

1891
1510

评测用例规模与约定：

对于所有评测用例，$1≤T≤1000，1≤X≤Y≤9999$。