Proqramçılar 1, 2, 4 və 8 rəqəmlərindən başqa heç bir rəqəmin iştirak etmədiyi ədədlərin uğurlu ədədlər olduğuna inanır. Məsələn 11, 8, 184, 1248 proqramçılara görə uğurlu ədədlərdir, lakin 147, 13, 808, 555 uğurlu ədədlər deyil.

Sizin tapşırığınız bəzən artan sırada k cı uğurlu ədədi tapmaq, bəzən isə verilmiş k ədədindən böyük olan ən kiçik uğurlu ədədi tapmaqdır. Siz bu iki növdə q sayda sorğuya düzgün cavab verən proqram yazmalısınız.

Giriş verilənləri

Birinci sətirdə bir tam ədəd q sorğuların sayı, növbəti q (1 ≤ q ≤ 104) sətrin hər birində isə iki tam ədəd, ti (ti = {1, 2}) və ki verilir. ti = 1 olduqda, siz artan sırada ki ci uğurlu ədədi, ti = 2 olduqda isə ki ədədindən böyük olan ən kiçik uğurlu ədədi tapmalısınız. Məlumdur ki:

• əgər ti = 1, olarsa 1 ≤ ki ≤ 2 * 109
• əgər ti = 2, olarsa 0 ≤ ki ≤ 1015

Çıxış verilənləri

Çıxışa hər bir sorğu üçün yeni sətirdən həmin sorğunun cavabını verin.

Nümunə

İlk bir neçə uğurlu ədəd aşağıdakılardır: 1, 2, 4, 8, 11, 12, 14, 18, 21, 22, 24, 28, 41, 42, 44, 48, ... .