D. Конные скачки
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Петя очень любит конные скачки. В скачках принимают участие лошади с номерами от l до r включительно. Петя хочет оценить вероятность выигрыша, для этого ему зачем-то нужно найти количество почти счастливых номеров лошадей. Номер называется почти счастливым, если в нем есть хотя бы две счастливые цифры, расстояние между которыми не превосходит k. От львовских ребят Петя узнал, что счастливые цифры — это цифры 4 и 7. Расстояние между цифрами — это модуль разности между их позициями в числе. Например, при k = 2 номера 412395497, 404, 4070400000070004007 являются почти счастливыми, а номера 4, 4123954997, 4007000040070004007 — не являются.

Петя подготовил 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 2
1 100
Выходные данные
4
Входные данные
1 2
70 77
Выходные данные
2
Входные данные
2 1
1 20
80 100
Выходные данные
0
0
Примечание

В первом примере имеется четыре почти счастливых числа: 44, 47, 74, 77.

Во втором примере только 74 и 77 попадают в данный отрезок.