Case #1: 1001
Case #2: 1
Case #3: 1011110110000100001