1110:Magic

      Kim is a magician, he can use n kinds of magic, number from 1 to n. We use string S_i to describe magic i. Magic S_i will make W_i points of damage. Note that W_i may change over time.

      Kim obey the following rules to use magic:

      Each turn, he picks out one magic, suppose that is magic S_k, then Kim will use all the magic i satisfying the following condition:

      1. W_i<=W_k

      2. S_k is a suffix of S_i.

      Now Kim wondering how many magic will he use each turn.

      Note that all the strings are considered as a suffix of itself.

First line the number of test case T. (T<=6)

For each case, first line an integer n (1<=n<=1000) stand for the number of magic.

Next n lines, each line a string Si (Length of S_i<=1000) and an integer Wi (1<=W_i<=1000), stand for magic i and it’s damage W_i.

Next line an integer Q (1<=Q<=80000), stand for there are Q operations. There are two kinds of operation.

“1 x y” means W_x is changed to y.

“2 x” means Kim has picked out magic x, and you should tell him how many magic he will use in this turn.

Note that different S_i can be the same.

For each query, output the answer.

1

5

abracadabra 2

adbra 1

bra 3

abr 3

br 2

5

2 3

2 5

1 2 5

2 3

2 2

3

1

2

1