В настоящее время широкое распространение получили системы двухфакторной аутентификации, в которой помимо основного пароля пользователю необходимо ввести один или несколько одноразовых паролей. Рассмотрим один из возможных алгоритмов генерирования таких паролей.
Пусть F(Q) – количество целых положительных чисел не больше Q, которые представимы в виде 2x - 2y при целых неотрицательных x, y. Упорядочим по возрастанию количества единичных бит в двоичном представлении все числа Q такие, что F(Q) = N. Если количество единичных бит в двух числах одинаково, большим считается то из них, значение которого больше. В качестве одноразового пароля выбирается K-е по порядку число.
Необходимо вычислить одноразовые пароли для T сессий аутентификации.
В первой строке задается число T — количество сессий аутентификации. В следующих T строках задается по два целых числа Ni и Ki — параметры алгоритма генерирования одноразового пароля.
В T строках выведите по целому числу — одноразовый пароль для соответствующей сессии аутентификации. Каждый пароль необходимо вывести по модулю 109 + 7. Если по заданным параметрам пароль сгенерировать невозможно, то необходимо вывести -1.
1
16 10
42
