Today is your best friend SJ’s birthday. You want to buy a birthday present for her. You want to buy such a present that she likes the most. You are very superstitious. You think that, SJ will love your gift, if the price of the present you buy is an interesting number (pretty weird isn’t it :P ). An interesting number is such a number that can be expressed as a product of Fibonacci numbers (not necessarily distinct). For example, 16 (2222), 40 (85) are interesting numbers but 7 is not. Input The first line of the input is an integer t (t ≤ 1000) denoting the number of test cases. Then t line follows. Each line has two integers a and b (1 ≤ a ≤ b ≤ 1018). Output For each case you have to print an integer in a line denoting the maximum interesting number between a and b (inclusive). Print ‘-1’ in case there is no solution. Sample Input 3 17 1 10 1 1000000000000000000 Sample Output 6 10 1000000000000000000