Uğurlu ədədlər

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 sorğuların q sayı, növbəti q (1 ≤ q ≤ 10^4) sətrin hər birində isə iki tam ədəd, t[i] (t[i] = {1, 2}) və k[i] verilir. t[i] = 1 olduqda, siz artan sırada k[i]-ci uğurlu ədədi, t[i] = 2 olduqda isə k[i] ədədindən böyük olan ən kiçik uğurlu ədədi tapmalısınız. Məlumdur ki:

• əgər t[i] = 1, olarsa 1 ≤ k[i] ≤ 2 * 10^9

• əgər t[i] = 2, olarsa 0 ≤ k[i] ≤ 10^15

Çıxış verilənləri

Hər bir sorğu üçün yeni sətirdə 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, ... .