Ключі
Місія Джона полягає в тому, щоб викрасти деякі важливі документи з одноповерхової будівлі. Він зміг отримати детальний план поверху будівлі, на якому вказано розташування всіх документів. У будівлі є двері, для відкриття яких потрібні ключі. У Джона є кілька ключів, а деякі ключі знаходяться всередині будівлі.
Допоможіть Джону визначити, скільки документів він може викрасти.
Вхідні дані
Перша строка містить кількість тестів, не більше 100. Кожен тест складається з:
одного рядка з двома цілими числами h і w (2 ≤ h, w ≤ 100): висота і ширина карти.
h рядків по w символів, що описують карту:
'.' - порожнє місце.
'*' - непрохідна стіна.
'$' - документ, який Джон хоче викрасти.
літера верхнього регістру - двері.
літера нижнього регістру - ключ, що відкриває двері з відповідною літерою верхнього регістру.
одного рядка з різними літерами нижнього регістру: ключі, які має Джон. Якщо у нього немає ключів, рядок містить "0".
Джон може вільно пересуватися з зовнішньої сторони будівлі. Для будь-яких дверей кількість ключів, які їх відкривають, може дорівнювати нулю, одному або бути більше одного. Для будь-якого ключа кількість дверей, які він відкриває, може дорівнювати нулю, одному або бути більше одного. Ключі можуть бути використані повторно.
Вихідні дані
Для кожного тесту виведіть в окремому рядку загальну кількість документів, які зможе викрасти Джон.