Given an integer x. Write a Program to count the number of integers between 1 to x (both inclusive) that don't have any adjacent 1's in their binary representations.
Input Format:
The first line contains T, number of test cases. (1<=T<=100)
Each of the next T lines contains the integer x. (1<= x <= 10^5)
Output Format: for each line of test cases print a number denoting the number of integers between 1 to x that doesn't have any adjacent 1's in their binary representation.
Sample Input :
1
5
Sample Output:
4
Explanation: 1,2,4,5 don't have consecutive 1's in their binary representation but 3 ("11") has consecutive 1's.
1,2,4,5 don't have consecutive 1's in their binary representation but 3 ("11") has consecutive 1's.