There is a cave of $N$ cells where each cell has a trap or is safe to land. From a cell $i$, you can jump to cells $i+1$ or $i+2$. Also, if number $i$ is special, then you can also jump from cell $i$ to cell $i+A$ where $A = number\; of\; primes\; in\; [1,i]$. A number $i$ can be special if $\frac{A}{i} \ge \frac{r1}{r2}$.

You are given the following:

• Some arbitrary numbers $r_1$ and  $r_2$
• The number of cells $N$ in the cave where each cell contains either '#' or '*'
• Details of the cave

Note: Here, '#' represents an empty cell and '*' means a trapped cell.

Your task is to determine the minimum number of steps that you have to walk to reach the $N^{th}$ cell. Initially, you are at cell 1.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two integers  $r_1$ and $r_2$.
• The second line of each test case contains an integer $N$.
• The third line contains a string of length $N$ representing $N$ cells where the first character of the string represents the first cell, second character represents the second cell, and so on. Each cell is either '#' or '*'.

Output format

For each test case, print the minimum number of steps that you have to walk to reach the $N^{th}$ cell. Print the output in a separate line.

If it is not possible to reach the  $N^{th}$ cell, then print "$No \; way!$" without quotes.

Constraints

$1 \le T \le 500$

$1 \le r_1, r_2 \le 10000$

$1 \le N \le 100000$

Note: For large input files, use faster input methods.