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

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

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

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
and f_invert = function (* f_invert l = f (invert l) *)
  | false :: ((false :: _) as not_t) -> false :: f not_t
  | false :: true :: not_t -> false :: false :: f_invert not_t
  | not_bl -> invert not_bl

let bombstrat s =
  print_bool_list (f (bool_list_of_string s))

let _ =
  let n = read_int () in
  for i = 1 to n do
    bombstrat (read_line ())
  done