Due to my work, I have to type several words every day. But the problem is that I'm too lazy to lift my finger up from keyboard, so I come up with a clever method: When I am going to type a word w, I first press on a key of lowercase alphabet on keyboard, then moving my finger along keys, and lift up my finger from keyboard. All keys my finger has passed through are pressed and corresponding letters are typed in order.
I can move my finger from a button to another only if they are adjacency" on keyboard. That is, they contain a common point on keyboard. A button is also adjacent to itself. For example, the button `p' is adjacent to `o', `l', `p', while the button `j' is adjacent to `u', `h', `n', `m', `k', `i', and `j'.
But not all the words can be typed by this way. So after surfing my finger on keyboard, I will get a string s that may be different to w. So in the end I will delete some redundant letters in s to form the word.
This method works well. Believe it or not, I type this problem by this method!
Nevertheless, I still want to optimize the method. Please help me to minimize the number of letters I should delete (It's also a hard work!).
The first line of input contains an integer T, the number of test cases in total. Following are T test cases, each in a line. Each test case contains a number l and a string s. l is the length of s, and the string s contains l lowercase alphabets (i.e. `a' to `z'). Similarly, I can only press the key `a' to `z' during the process. Other keys, for example, space bar, numbers (`1'), signals(`?'), and special keys(`alt'), are forbidden.
1<=T<=100
1<=l<=1000
You should output the minimum number of letters I should delete for each word.