该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师发现了一个有趣的数学规律：有些数字的平方的各位数字之和，恰好等于这个数字本身。 现在给定lr区间，问区间内有多少个数字满足

Format

Input

第一个行一个数字$T( \leq 10^3)$，表示测试组数

对于每组测试给定一个$lr(1\leq l \leq r \leq 10^9)$，表示区间范围

Output

对于每个区间回答符合的数字个数

Samples

1
1 1

1

Limitation

1s, 1024KiB for each test case.