Jack is a very good student like Harsh and he could solve problems easily. Today he is struck by a problem and needs your help. The problem statement is : Jack will toss a coin x times and write down the sequence of outcomes. Then he start counting all the prime numbers between a given range from m to n (both inclusive) and with every prime number there is an associated value of coin i.e. Head (H) and Tail (T). If Heads then include the prime number in counting otherwise discard it. Jack will repeat the outcome sequence that he got via tossing the coin.

Input : The first line contains T (number of test cases):

Second line contains m, n, x followed by x lines.

Again m, n, x followed by x lines This will continue for T times.

For Test case:

1
1 10 2

the output will be evaluated as shown in the image below:

Here, two numbers i.e. 2 and 5 have respective Heads(H) other wise discarded.

Hence, Output will be:

2

Input constraints

0<T<10

0<m<n

0< n < 10^14 (surprise)

0<x<10

0<(n-m)<10000000

Input:

3
1 10 2
H
T
20 35 1
H
1 20 5
H
H
T
H
T

*Output: *

2
3
5