Bilet Çəkilişi

Bon Jovi Turu 2013 konsertlərinin təşkilatçıları biletləri lotereya üsulu ilə satmağa qərar veriblər. Qaydalar sadədir. Hər konsert üçün azarkeşlər biletlərə onlayn müraciət edirlər və cavab olaraq unikal rezervasiya nömrələri alırlar. Hər konsert üçün verilən nömrələrin 0-dan başlayaraq ardıcıl qeyri-mənfi tam ədədlər olması vacibdir. Lakin təşkilatçılar rezervasiya nömrələrini təsadüfi seçmək üçün istifadə etdikləri pseudo təsadüfi generatorun çox yavaş olduğunu aşkar etdilər. Generatora zənglərin sayını azaltmaq üçün onlar biletləri paylamaq üçün qəribə, lakin ədalətli bir üsul tapdılar.

Konsert üçün rezervasiya başa çatdıqdan sonra təşkilatçılar müraciətlərin sayını M olaraq müəyyən edirlər və {0, ..., M - 1} aralığından təsadüfi bir tam ədəd Z seçirlər (unutmayın, azarkeşlər 0-dan M - 1-ə qədər tam ədədlər alırlar). Z təşkilatçıların təsadüfi seçməli olduğu yeganə ədəddir! Seçim qaydalarını tamamlamaq üçün təşkilatçılar seçilmiş biletlərin sayına birbaşa təsir edən r > 0 tam ədədini müəyyən edirlər.

İndi, Z və r istifadə edərək, biletlər aşağıdakı kimi deterministik olaraq seçilir. Rezervasiya nömrələri 0, ..., M - 1 və Z nömrəsi üçün, onların uzunluğu n olan onluq təsvirləri nəzərə alınır, burada n - M - 1-in sıfırdan əvvəlki sıfırlar olmadan təsvirinin uzunluğudur. Beləliklə, qalan nömrələrin onluq təsvirləri, lazım olduqda, sıfırdan əvvəlki sıfırlarla soldan doldurulur. Əgər z[1] ... z[n] Z üçün belə bir təsviri göstərirsə, onda a[1] ... a[n] nömrəsinin sahibi bileti alır, əgər və yalnız z[1] ... z[n] və a[1] ... a[n] eyni mövqedən başlayan uzunluğu r və ya daha çox olan ümumi ardıcıl alt sətri varsa. Formal olaraq desək, o və ya o bileti alır, əgər 1 ≤ i ≤ n - r + 1 olan bir indeks i varsa, belə ki, z[i] ... z[i+r-1] = a[i] ... a[i+r-1]. Məsələn, əgər Z = 56743 və r = 3 olarsa, 06740 rezervasiya nömrəsi olan azarkeş bileti alır, lakin 56143 olan azarkeş almır.

Sizin vəzifəniz təşkilatçılara verilmiş M, Z və r ədədləri üçün bu şəkildə seçilmiş biletlərin dəqiq sayını qiymətləndirməkdə kömək etməkdir.

Giriş

Birinci sətir konsertlərin sayını C (1 ≤ C ≤ 5000) ehtiva edir. Sonra C sətir gəlir, hər biri üç tam ədəd M, Z və r (0 < M ≤ 10^18, 0 ≤ Z ≤ M - 1 və r ≥ 1) ehtiva edir. r-in M - 1-in onluq təsvirinin uzunluğundan kiçik və ya bərabər olduğunu təhlükəsiz şəkildə qəbul edə bilərsiniz.

Çıxış

Hər konsert üçün, bilet çəkilişi zamanı seçilmiş biletlərin sayını ehtiva edən bir sətir çap edin.