Petya非常喜欢赛马。编号从 l 到 r 的马匹参加比赛。彼佳想要评估胜利的可能性;出于某种原因,要做到这一点,他需要知道几乎幸运的马匹的数量。近幸运数是至少有两个幸运数字且其之间的距离不超过 k 的整数。佩蒂亚从利沃夫的一些朋友那里得知,幸运数字是数字4和7。数字之间的距离是它们在马数中的位置之间的绝对差。例如,如果 k = 2,则数字 412395497、404、4070400000070004007 几乎是幸运的,而数字 4、4123954997、4007000040070004007 则不是。
Petya 准备了 t 区间 [li, ri] 并发明了数字 k,它们都是通用的。你的任务是找出每个部分中有多少个接近快乐的数字。由于答案可能相当大,因此输出它们对 1000000007 (109 + 7) 取模。
输入
第一行包含两个整数 t 和 k (1 ≤ t, k ≤ 1000) — 线段的数量以及相应数字之间的距离。接下来的 t 行包含整数对 li 和 ri (1 ≤ l ≤ r ≤ 101000)。所有数字均不带前导零。每行中的数字均由一个空格字符分隔。
输出
输出 t 行。在每一行中打印一个整数——相应段的答案模 1000000007 (109 + 7)。
示例
输入 #1
1 2 1 100
输出 #1
4
输入 #2
1 2 70 77
输出 #2
2
输入 #3
2 1 1 20 80 100
输出 #3
0 0
注意
在第一个样本中,四个接近幸运的数字是 44、47、74、77。
在第二个示例中,给定段中只有 74 和 77。