Maraqlı ardıcıllıq

Verilən 011212201220200112... ardıcıllığı belə yaranır: əvvəlcə 0 yazılır, sonra isə aşağıdakı əməliyyat təkrarlanır: artıq yazılmış hissə sağ tərəfə əlavə edilir, burada 0 1 ilə, 1 2 ilə, 2 0 ilə əvəz olunur, yəni

0 → 01 → 0112 → 01121220 → ...

Sizdən bu ardıcıllıqda m-ci rəqəmi tapmaq tələb olunur.

Giriş məlumatları

Birinci sətir testlərin sayı n (1 ≤ n ≤ 1000) ehtiva edir. Daha sonra n sətir gəlir, hər biri m (1 ≤ m ≤ 2^63 - 1) - ardıcıllıqda axtarılan rəqəmin nömrəsini ehtiva edir.

Çıxış məlumatları

Hər bir test üçün təsvir olunan ardıcıllıqda m-ci yerdə duran rəqəmi ayrıca sətirdə çıxarın.