Binary string of an integer is the string representation of it in binary without any leading zero. For example binary string of 5 is “101” where binary string of 13 is “1101”.
A substring is any contiguous portion of a string. For example “01” is a substring of “1011” but “00” and “111” are not.
Given A, B and P . Find the smallest integer S such that P is a binary substring of S and A ≤ S andS≤B. 1≤A,B,P ≤1015 andA≤B.
For example, A = 9, B = 20, P = 5 (“101”). 10 (“1010”) is the smallest number in that range containing P as a substring.
Input
Input starts with an integer T ≤ 1000, denoting the number of test cases followed by T test cases. Each of the following T lines will contain three space separated integers A, B and P .
Output
Foreachcase,printalineoftheform‘Case ’,wherexisthecasenumberandSisthe number (in decimal). If there is no valid S, then output ‘NONE’ (quotes for clarity).
Sample Input
4
10 20 5
10 100 9
1 1000 7
10 20 21
Sample Output
Case 1: 10
Case 2: 18
Case 3: 7
Case 4: NONE