Problem D

効率的な問題セット

あなたは来たるプログラミングコンテストの問題セットを検討中である． 問題セットは，それぞれ正整数の配点を定めた 1 つ以上の問題で構成される． 各参加者の得点は，その参加者が正解した問題の配点の総和とする．

問題セットの配点の合計はコンテスト主催者の定めた満点に等しくなければならない． また，コンテストのスポンサー企業のいくつかは，特定の得点ちょうどに最初に到達した参加者に特別賞を与えたいという． このために，スポンサー特別賞の対象となる全ての得点について，それらがある時点での参加者の得点となり得るように問題セットを構成する必要がある．

あなたはまだ問題を 1 つも準備しておらず，問題セットの配点を決めた後で準備を始めるつもりである． 問題をたくさん準備するのは大変なので，なるべく少ない問題数で上記の要件を満たしたい． たとえば，満点が 7 点で特別賞得点が 2 点と 5 点である場合，配点が 2 点の問題と 5 点の問題を 1 つずつ準備すれば，2 問で要件を満たせる． 一方，満点が 7 点で特別賞得点が 2 点と 4 点である場合，3 問（たとえば，配点が 2 点の問題 2 つと 3 点の問題 1 つ）が必要となる．

要件を満たすような問題数の最小値を求めよ．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n
s

n はコンテストの満点（全問題の配点の合計）を表す． n は正の整数であり，100 を超えない． s は参加者の得点として現れ得るべき値を表す． s は o, x からなる長さ (n + 1) の文字列であり，その (k + 1) 文字目は「参加者がちょうど k 点を獲得可能でなければならない」場合に o，その必要はない，すなわち「参加者がちょうど k 点を獲得可能でも不可能でも構わない」場合に x である． s の最初と最後の文字は必ず o である．

入力の終わりは，1 つのゼロからなる行で表される． 入力に含まれるデータセットは 100 個以下である．

Output

各データセットについて，要件を満たすような問題数の最小値を 1 行に出力せよ．

Sample Input

3
ooxo
5
oxxxxo
7
oxoxoxxo
7
oxoxxoxo
8
oxxooooxo
0

Output for the Sample Input

2
1
3
2
4

---