題目描述

你的朋友小濠在數學堂學了有關於字串的性質。

小濠學用了長度 L 的字串 C 含有大寫英文字母是嚴格單調遞增，如果每對英文字母的 index i 和 j (1 ≤ i < j ≤ L ( index 由 1 開始 ) )，在位置 i 的英文字比在位置 j 的英文字的位置前。

例如，字串 ABC 和 ADF 就是嚴格單調遞增，字串 AAB 和 FDA 就不是。

現在小濠教會了你這個性質，小濠打算挑戰你：已知長度為 N 字串 S，你要找出在每個位置 1 ≤ i ≤ N，最長的嚴格單調遞增的子字串在位置 i 結束是多長？

輸入格式

輸入的第一行有一個整數T，T是測試數據組數 (1 ≤ T ≤ 100)

每個測試數據有2行

第一行含有一個整數N，N是字串的長度 (1 ≤ N ≤ 200000)

第二行含有長度為N的字串S，由大寫英文字母組成。

每個測試數據，輸出一行含有 Case #x: y1 y2 ...yn，x是測試數據的編號（從1開始），yi是嚴格單調遞增子字串最長長度結束於位置 i 。

2
4
ABBC
6
ABACDA

Case #1: 1 2 1 2
Case #2: 1 2 1 2 3 1

在Case #1中，最長嚴格單調遞增子字串在位置 1 結束是 A 。最長嚴格單調遞增子字串在位置 2，3 和 4 結束分別是 AB，B 和 BC 。

在Case #2中，最長嚴格單調遞增子字串在每個位置結束的是 A，AB，A，AC，ACD 和 A。