Петягийн ихэд дурладаг морины уралдаанд $l$-ээс $r$ хүртэл дугаартай моринууд нэг дор уралддаг. Петя түрүүлэх магадлалтай морьнуудыг тодорхойлохыг хүсэв. Тэгээд тодорхой шалтгааны улмаас "бараг азын дугаар"-тай морьнуудын тоог мэдэхийг хүсэв. "Бараг азын дугаар" гэдэг нь аравтын бичиглэлд нь ядаж хоёр азын цифр $k$-аас хэтрэхгүй зайтай байрлаж орсон тоог хэлнэ.

Петя Львов дахь найзаасаа $4$ ба $7$ бол азын цифрүүд гэдгийг мэдэж авсан бөгөөд цифрүүдийн хоорондын зай гэдэг нь цифрүүдийн байрлалыг илэрхийлэх дугааруудын ялгаварыг тооцно.

Жишээ нь $k = 2$ үед $412395497$, $404$, $4070400000070004007$ тоонууд нь бараг азын дугаар болох ба $4$, $4123954997$, $4007000040070004007$ тоонууд нь биш.

Петя $t$ ширхэг $[l_i, r_i]$ завсар бэлтгэсэн ба $k$ тоог тооцоолж олжээ. Одоо танаас хүсч байгаа түүний хүсэлт бол завсар бүр дэхь бараг азын дугаарын тоог олох юм. Хариу хэт их гарж болзошгүй тул $1000000007$-д ($10^9+7$) хуваасан үлдэгдлийг Петяд мэдээллэхэд болно.

Оролт

Эхний мөрөнд $t$ ба $k$ ($1 ≤ t, k ≤ 1000$) хоёр тоо. Дараагийн $t$ мөрөнд мөр бүрд $l_i$, $r_i$ ($1 ≤ l ≤ r ≤ 10^{1000}$) тоонууд зайгаар тусгаарлагдан өгөгдөнө. Оролтын өгөгдөл дэхь тоонууд зөв бичиглэлтэй буюу тэгээр эхлэхгүй.

Гаралт

$t$ мөрөнд мөр бүрт хариу болох тоог $1000000007$-д ($10^9+7$) хуваасан үлдэгдэл байна.

In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.

In the second sample, only 74 and 77 are in the given segment.