У нас є два рядки \(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