题目描述

彼佳非常喜欢赛马，有编号从 $l$ 到 $r$ 的马参加比赛。幸运数字为 $4$ 或 $7$。有机会赢的马的编号满足在这一串数字中，存在两个幸运数字，它们之间的距离不超过 $k$（两个相邻的数字之间的距离为 $1$）。问有机会赢的马的编号一共有几个。输出答案对 $10^9+7$ 取模。

输入格式

第一行两个整数 $t,k$，$t$ 表示数据组数，$1 \le t, k \le 1000$。

接下来 $t$ 行，每行两个整数 $l,r$，$1 \le l \le r \le 10^{1000}$。

输出格式

$t$ 行，每行一个整数表示第 $i$ 组数据的答案。

1 2
1 100

4

1 2
70 77

2

2 1
1 20
80 100

0
0