题目描述

薯条哥拥有一个长度为$n$的01串，现在他想知道，对于每个字符，在它前面的最近的不同字符的下标是多少？字符串下标从1开始。

输入描述

本题为多组测试数据，第一行输入一个正整数$T(1\le T\le 100)$，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数$(n(1\le n\le 1000)$，代表初始 01串的长度。

第二行输入一个长度为$n$的01串，代表初始字符串。

输出描述

对于每组测试数据，一行输出$n$个整数$a_1,a_2,...a_n$，其中$a_i$代表初始字符串中第$i$个位置的字符前面，最近的不同字符的下标是$a_i$，特殊的，如果前面不存在不同字符，则输出-1表示不存在。

样例

输入

1
4
1101

输出

-1 -1 2 3

样例解释

第一个字符为1，前面没有0，输出-1

第二个字符为1，前面没有0，输出-1

第三个字符为0，左边有一个1，输出2

第四个字符为1，左边有一个0，输出3