Base… -2 ?

As we know, every number has a limited and unique writing in every base n for b ≥ 2. Given N numbers n, return their writing in base -2.

Input

  • -10^10 ≤ n ≤ 10^10
  • 1000 ≤ N ≤ 10000

Examples

Input :

-2
5
10
967

Output :

10
101
11110
10011011011

I/O SU

Évènement organisé par ALIAS