Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.

В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число K_i — номер позиции в последовательности (1 ≤ K_i ≤ 2³¹ − 1).

Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером K_i.