Problem: You are given a binary string s consisting of n zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of s. The second line of the test case contains n characters '0' and '1' — the string s.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer: in the first line print one integer k (1 ≤ k ≤ n) — the minimum number of subsequences you can divide the string s to. In the second line print n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ k), where a_i is the number of subsequence the i-th character of s belongs to.

If there are several answers, you can print any.

Example

Input


4
4
0011
6
111111
5
10101
8
01010000


Output


2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void _print(long long t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(long double t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(unsigned long long t) { cerr << t; }
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
  cerr << "]" << endl;
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
  cerr << "]" << endl;
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]"
       << "]" << endl;
}
template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int f = 0;
  cerr << '{';
  for (auto& i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
template <typename T>
void print(vector<vector<T>>& v) {
  for (vector<T>& vv : v) {
    for (T& i : vv) cout << i << " ";
    cout << '\n';
  }
}
template <typename T>
void print(vector<T> v) {
  for (T i : v) cout << i << " ";
  cout << '\n';
}
template <typename T>
void read(vector<T>& v) {
  for (T& i : v) cin >> i;
}
template <typename T>
void read(T&& t) {
  cin >> t;
}
template <typename T, typename... Args>
void read(T&& t, Args&&... args) {
  cin >> t;
  read(forward<Args>(args)...);
}
template <typename T>
void print(T&& t) {
  cout << t << '\n';
}
template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
  cout << t << " ";
  print(forward<Args>(args)...);
}
template <class T>
void print(set<T>& a) {
  for (auto& e : a) cout << e << " ";
  cout << "\n";
}
template <class T, class V>
void print(vector<pair<T, V>>& a) {
  for (auto& e : a) cout << e.first << " " << e.second << "\n";
}
template <typename T>
vector<T>& operator--(vector<T>& v) {
  for (auto& i : v) --i;
  return v;
}
template <typename T>
vector<T>& operator++(vector<T>& v) {
  for (auto& i : v) ++i;
  return v;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& i : v) is >> i;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& i : v) os << i << ' ';
  return os;
}
long double pie = 3.141592653589793238462643383279502884197169399;
bool isprime(long long n) {
  if (n <= 1) {
    return false;
  }
  if (n <= 3) {
    return true;
  }
  if (n % 2 == 0 || n % 3 == 0) {
    return false;
  }
  for (long long i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
long long modInverse(long long n, long long mod) {
  return binpow(n, mod - 2, mod);
}
long long comb(long long n, long long r, long long p, vector<long long>& fac) {
  if (r == 0 or n == r) return 1;
  if (r > n) return 0;
  return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) %
         p;
}
set<long long> divisors(long long n) {
  set<long long> s;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      s.insert(i);
      s.insert(n / i);
    }
  }
  return s;
}
set<long long> primess;
void seive() {
  vector<int> is_prime(1e6 + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i * i <= 1e6; i++) {
    if (is_prime[i]) {
      for (int j = i * i; j <= 1e6; j += i) is_prime[j] = false;
    }
  }
  for (int i = 2; i <= 1e6; i++) {
    if (is_prime[i]) {
    }
  }
}
map<long long, long long> primeFactors(long long n) {
  map<long long, long long> m;
  while (n % 2 == 0) {
    m[2]++;
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      m[i]++;
      n = n / i;
    }
  }
  if (n > 2) m[n]++;
  return m;
}
long long factorial(long long n) {
  long long res = 1;
  for (long long i = 1; i <= n; i++) {
    res *= i;
  }
  return res;
}
long long C(long long n, long long r) {
  long long res = 1;
  for (long long i = 0; i < r; i++) {
    res = res * (n - i) / (i + 1);
  }
  return res;
}
long long toint(string s) {
  long long num = 0;
  for (long long i = 0; i < s.size(); i++) {
    num = num * 10 + s[i] - '0';
  }
  return num;
}
long long sumstring(string s) {
  long long sum = 0;
  for (long long i = 0; i < s.size(); i++) {
    sum += (s[i] - '0');
  }
  return sum;
}
long long sumdigit(long long n) {
  long long sum = 0;
  while (n) {
    long long rem = n % 10;
    sum += rem;
    n /= 10;
  }
  return sum;
}
string tobinary(long long x) {
  string a;
  while (x > 0) {
    a += (x % 2) + '0';
    x /= 2;
  }
  reverse(begin(a), end(a));
  return a;
}
long long todecimal(string x) {
  long long sum = 0;
  long long n = x.size();
  long long j = 0;
  for (long long i = n - 1; i >= 0; i--) {
    if (x[i] == '1') {
      sum += (1LL << j);
    }
    j++;
  }
  return sum;
}
long long ceil(long long n, long long k) { return (n + k - 1) / k; }
bool ispalin(string s) {
  long long n = s.size();
  for (long long i = 0; i < n; i++) {
    if (s[i] != s[n - i - 1]) {
      return false;
    }
  }
  return true;
}
bool ispermutation(vector<long long> p) {
  sort(begin(p), end(p));
  for (long long i = 1; i <= p.size(); i++) {
    if (p[i - 1] != i) return false;
  }
  return true;
}
bool isperfect(long long x) {
  long long a = sqrtl(x);
  return a * a == x;
}
bool issubsequence(string t, string x) {
  long long j = 0;
  for (long long i = 0; i < x.size(); i++) {
    if (x[i] == t[j]) {
      j++;
    }
    if (j == t.size()) break;
  }
  return j == t.size();
}
long long power(long long base, long long exponent) {
  long long res = 1;
  while (exponent) {
    if (exponent & 1) {
      res = res * base;
    }
    base *= base;
    exponent >>= 1;
  }
  return res;
}
struct Cmp {
  bool operator()(const pair<long long, long long>& l,
                  const pair<long long, long long>& r) const {
    return l.second < r.second;
  }
};
bool comp(string s1, string s2) {
  for (long long i = 0; i < s1.size(); i++) {
    if (s1[i] == s2[i]) continue;
    return s1[i] < s2[i];
  }
  return false;
}
double area(double dX0, double dY0, double dX1, double dY1, double dX2,
            double dY2) {
  double dArea = ((dX1 - dX0) * (dY2 - dY0) - (dX2 - dX0) * (dY1 - dY0)) / 2.0;
  return (dArea > 0.0) ? dArea : -dArea;
}
long long mod = 1e9 + 7;
long long add(long long a, long long b) {
  a = a % mod;
  b = b % mod;
  return (((a + b) % mod) + mod) % mod;
}
long long mul(long long a, long long b) {
  a = a % mod;
  b = b % mod;
  return (((a * b) % mod) + mod) % mod;
}
long long sub(long long a, long long b) {
  a = a % mod;
  b = b % mod;
  return (((a - b) % mod) + mod) % mod;
}
long long C(long long n, long long r, long long mod) {
  long long ans = 1;
  if (n - r < r) r = n - r;
  for (long long i = n; i > n - r; i--) ans = mul(ans, i);
  for (long long i = 1; i <= r; i++) ans = mul(ans, modInverse(i, mod));
  return ans;
}
struct edge {
  long long src, dest;
  long long cost;
};
void solve() {
  long long n;
  cin >> n;
  string s;
  cin >> s;
  set<long long> one, zero;
  vector<long long> a(n);
  for (long long i = 0; i < n; i++) {
    if (s[i] == '1')
      a[i] = 1;
    else
      a[i] = 0;
  }
  for (long long i = 0; i < n; i++) {
    if (a[i] == 0) {
      zero.insert(i);
    } else
      one.insert(i);
  }
  vector<long long> pos(n);
  vector<long long> vis(n);
  long long count = 1;
  for (long long i = 0; i < n; i++) {
    if (vis[i] == 0) {
      long long flag = 1 - a[i];
      vis[i] = 1;
      pos[i] = count;
      if (a[i] == 0) {
        zero.erase(i);
      } else {
        one.erase(i);
      }
      long long j = i;
      while (1) {
        if (flag) {
          auto it = one.lower_bound(j);
          if (it != one.end()) {
            j = *it;
            pos[j] = count;
            vis[j] = 1;
            one.erase(it);
            flag = 1 - flag;
          } else
            break;
        } else {
          auto it = zero.lower_bound(j);
          if (it != zero.end()) {
            j = *it;
            pos[j] = count;
            vis[j] = 1;
            zero.erase(it);
            flag = 1 - flag;
          } else
            break;
        }
      }
      count += 1;
    }
  }
  print(count - 1);
  print(pos);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  clock_t start = clock();
  long long t;
  cin >> t;
  while (t--) {
    solve();
  }
  clock_t stop = clock();
  double elapsed = (double)10 * (stop - start) / CLOCKS_PER_SEC;
  cerr << setprecision(5) << fixed;
  cerr << "\nProcess finished in: " << elapsed << "ms\n";
}