You have recently read about superdromes. Superdromes are those numbers that are palindromic in both binary and decimal representation.
The number represented in binary representation is up to its most significant bit that is . For example, will be represented as , is represented as , and so on.
Your task is to determine the number of superdromes that are less than or equal to for provided .
Input format
Output format
Print a single integer that represents the number of superdromes that is less than or equal to for each query. Print the answer for each query as space-separated integers.
Constraints
1 and 3 are superdromes while 2 is not a superdrome.