Tránh Bẫy

Trong một chuyến thám hiểm hang động, FullHouse Dev đã phát hiện ra một hang động cổ đầy những cạm bẫy. Để vượt qua thử thách này, họ cần tính toán cẩn thận từng bước đi để đến được đích an toàn. Hãy cùng xem họ sẽ giải quyết thử thách này như thế nào.

Bài toán

Có một hang động gồm \(N\) ô, mỗi ô hoặc có bẫy hoặc an toàn để đặt chân. Từ một ô \(i\), bạn có thể nhảy đến ô \(i+1\) hoặc \(i+2\). Ngoài ra, nếu số \(i\) là số đặc biệt, bạn có thể nhảy từ ô \(i\) đến ô \(i×k\) với \(k\) là một số cho trước. Một số \(i\) được gọi là đặc biệt nếu \(i\) chia hết cho \(x\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu của mỗi test case chứa hai số nguyên \(x\) và \(k\)
• Dòng thứ hai chứa số nguyên \(N\)
• Dòng thứ ba chứa một chuỗi độ dài \(N\) biểu diễn \(N\) ô, trong đó '#' là ô an toàn và '*' là ô có bẫy

OUTPUT FORMAT:

• Với mỗi test case, in ra số bước tối thiểu cần thực hiện để đến được ô thứ \(N\)
• Nếu không thể đến được ô thứ \(N\), in ra "No way!"

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq x, k \leq 10^9\)
• \(1 \leq N \leq 10^5\)

Ví dụ

INPUT

3
1 2
8
########
1 5
5
#***#
2 3
11
#*#*#*#*#*#

OUTPUT

3
No way!
5

Giải thích

• Test case 1: Có thể đến đích trong 3 bước: nhảy đến ô 2, rồi đến ô 4, và cuối cùng dùng tính chất đặc biệt để nhảy đến ô 8.
• Test case 2: Không có cách nào để đến được ô cuối cùng.
• Test case 3: Cần 5 bước để đến đích: nhảy lần lượt qua các ô 1 → 3 → 5 → 7 → 9 → 11.