Fancy That!

3.3

3 votes
Algorithms, Dynamic Programming, Medium
Problem

Misha has decided to come up with the following puzzle to ask her friends:

Find the count of fancy numbers in the range . Fancy numbers have an interesting property. The property states that the sum of numbers got as the result of adding all the subsequences that can be formed from the given number will be even.

For example, the number  is a fancy number as the sum of numbers that are formed by all of its subsequences is calculated as: . Since is an even number, the number is considered to be fancy.

Input format

  • First line: An integer  denoting the number of test cases
  • Each of the next   lines: Two space-separated integers  and


Output format

  • Print the answer for each test case in a separate line.

Constraints

Sample Input
1
8 11
Sample Output
1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Subsequence Sum for is  which is even.
Subsequence Sum for is which is odd.
Subsequence Sum for  is  which is odd.
Subsequence Sum of is which is odd.

Hence, there is only one number in the range which is fancy.

Editor Image

?