(* http://www.spoj.pl/problems/LWAR/ *)

let rec invert = function
  | [] -> []
  | h :: q -> (not h) :: invert q

let rec f = function
  | true :: ((true :: _) as t) -> true :: f (invert t)
  | true :: false :: t -> true :: true :: f t
  | bl -> bl

let _ =
  let bool_list_of_string s =
    let n = String.length s in
    let rec aux i =
      if i < n then (s.[i] = '1') :: aux (i + 1)
      else [] in
    aux 0 in

  let print_bool_list l =
    List.iter (fun x -> print_char (if x then '1' else '0')) l;
    print_newline () in

  let n = read_int () in
  for i = 1 to n do
    let s = read_line () in
    print_bool_list (f (bool_list_of_string s))
  done