What-The-Fatherland — это странная страна! Все номера телефонов там представляют собой строки, состоящие из строчных букв латиницы. Вдвойне странно то, что один номер телефона может относиться к нескольким медведям!
В этой стране есть рок-группа под названием CF, состоящая из n медведей (включая Майка), пронумерованных от 1 до n.
Номер телефона i-го члена CF — si. 17 мая в стране выходной под названием День звонков. В последний День Звонков каждый медведь позвонил по всем номерам, являющимся построками его номера (возможно, по некоторому номеру пришлось позвонить несколько раз). В частности, каждый позвонил себе (это действительно странная страна!).
Обозначим как call(i, j) количество раз, которое i-й участник CF позвонил j-ому участнику CF.
У Майка есть q запросов, которые он хочет задать вам. В каждом запросе он дает вам номера l, r и k, а вы должны назвать ему число
