405859: GYM102136 A One-time passwords

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. One-time passwordstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

First 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.

1 ≤ T ≤ 105
1 ≤ Ni, Ki ≤ 1018
Output

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.

ExampleInput
1
16 10
Output
42

加入题单

上一题 下一题 算法标签: