Because of its fun mechanics, Super Bario World is a hit among gamers from Minas Gerais. In the game, Bario moves through levels made of $$$N$$$ blocks, each of which may be either a solid block or a hole. The goal is to get from the start of the level (block $$$1$$$) to the end (block $$$N$$$) without falling into any hole. Bario can run over solid blocks and, to avoid holes, he can jump over them.
Bario wears boots with an energy charge, initially equal to $$$1$$$. While running, he charges the boots so he can jump farther – each solid block Bario runs over adds one unit of charge to his equipment. A jump with charge $$$v$$$ lets Bario go from block $$$b$$$ to any block from $$$b+1$$$ to $$$b+v$$$; after landing, the boots lose their energy and return to their initial charge of $$$1$$$.
Compute the minimum number of jumps Bario needs to reach position $$$N$$$, or report that it is impossible.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 5 \times 10^{5}$$$), the number of test cases. It is guaranteed that the sum of the values of $$$N$$$ is less than $$$5 \times 10^{5}$$$.
Then $$$T$$$ pairs of lines follow. The first line of each pair contains $$$N$$$ ($$$2 \leq N \leq 5 \times 10^{5}$$$), the length of the level, and the second contains a string of $$$N$$$ characters representing the blocks of the level: x for a solid block and . for a hole. It is guaranteed that blocks $$$1$$$ and $$$N$$$ are solid.
Print the minimum number of jumps Bario needs to reach the end of the level, or $$$-1$$$ if it is impossible.
216xxxxxxx.xxxx.x.x3x.x
2 -1
Explanation for example 1
In the first test case, one possible solution with only two jumps has Bario:
- Run from position $$$1$$$ to position $$$5$$$, charging the boots to energy $$$5$$$, and jump, landing at position $$$9$$$. After landing, his boots go back to energy $$$1$$$.
- Run from position $$$9$$$ to position $$$12$$$, charging the boots to energy $$$4$$$, and jump to the end.
