405859: GYM102136 A One-time passwords
Description
Nowadays two-factor authentication, when user is required to use primary password and one or more one-time passwords, is becoming more widespread. Consider one of possible ways to generate such kind of passwords.
Let F(Q) be a number of positive integers not greater than Q, which can be represented as 2x - 2y when x, y are non-negative integer numbers. Consider all possible numbers Q such as F(Q) = N and sort them in ascending order by number of one-bits in their binary representation. If two numbers have the same number of one-bits in binary representation, they should be compared by their values. Proposed algorithm chooses K-th number in this sorted sequence.
You are required to find one-time passwords for T authentication sessions.
InputFirst line contains an integer number T — number of authentication sessions. Next T lines contain two numbers Ni and Ki each — parameters of one-time password generation algorithms.
T lines containing one integer number each — one-time password for corresponding authentication session. Each password should be computed in modulo 109 + 7. If it is impossible to generate one time password, -1 should be printed.
ExampleInput1Output
16 10
42