m@main=getLine>>=putStrLn.f>>m
f[]=[]
f x=g(2^n+h c)++f z where(b,y)=[2*a+1|a<-[0..],x!!a>'0']!!0%x;n=h b-1;(c,z)=n%y
(%)=splitAt
h=foldl(\a b->2*a+read[b])0
g n=fst$1&2where a&b|a>n=("1",n)|1>0=b&(a+b)#a
(x,n)#a=("01"!!div n a:x,mod n a)