У нас є два рядки ~S~ і ~P~, причому ~P~ є підрядком рядка ~S~. Рядки містять лише малі англійські символи. Ваша програма має виконати ~Q~ запитів над підрядком ~S~. Кожен запит містить ціле додатне ~N~ та символ нижнього регістру ~C~. Для кожного запиту ~Q_i~ треба замінити символ з індексом ~N~ (індекси починаються з 0) рядка ~S~ на символ ~C~. Запити виконуються у порядку їх слідування. Вам треба знайти мінімальну кількість запитів для того, що ~P~ перестав бути підрядком ~S~.

Якщо рядок ~P~ буде підрядком ~S~ навіть після виконання всіх запитів ~Q~, тоді треба вивести -1.

Формат вхідних даних

Перший рядок містить одне ціле число ~T~ (~1 \le T \le 50~) - кількість тестів.

Перший рядок кожного тесту містить один рядок ~S~ (~1 \le |S| \le 2\cdot10^5~).

Другий рядок кожного тесту містить один рядок ~P~ (~1 \le |P| \le |S|~)

Третій рядок кожного тесту містить одне ціле число ~Q~ (~1 \le Q \le |S|~) - кількість запитів.

Наступні рядки Q тесту містять ~N~ (~0 \le N \le |S|~) і ~C~, які розділені пропуском.

Формат вихідних даних

Для кожного тесту вивести відповідну відповідь.

Приклад вхідних даних

2
abcdefg
bc
3
0 d
1 q
2 z
abcdefg
cde
2
0 z
1 k

Приклад вихідних даних

2
-1