In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible.
For more information read https://en.wikipedia.org/wiki/Mealy_machine
Q0 is the starting state.
You are given a String and find the output for the above mealy machine.
Example:
S=”1010”
(q0,”1010”,””)-> (q2,”010”,”0”)->(q1,”10”,”01”)->(q2,”0”,”011”)->(q1,””,”0111”)
Output: “0111”
Input format
- First line: An integer N denoting the number of test cases
- Each test case contains a string
Output format
For each test case, print the output of the mealy machine
Constraints
1<=N<=1000
1<LEN(S)<=1000
