Fancy That!
Tag(s):

## Algorithms, Dynamic Programming

Problem
Editorial
Analytics

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

Find the count of fancy numbers in the range $[L, R]$. 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 $202$ is a fancy number as the sum of numbers that are formed by all of its subsequences is calculated as: $2 + 0 + 2 + 20 + 02 + 22 + 202 = 250$. Since $250$ is an even number, the number $202$ is considered to be fancy.

Input format

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

Output format

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

Constraints

$1 \le T \le 100$

$1 \le L,\ R \le 10^{10}$

SAMPLE INPUT
1
8 11

SAMPLE OUTPUT
1

Explanation

Subsequence Sum for $8$ is $8$  which is even.
Subsequence Sum for $9$ is $9$ which is odd.
Subsequence Sum for $10$ is $11 \ (10 + 1 + 0)$ which is odd.
Subsequence Sum of $11$ is $13 \ (11 + 1 + 1)$ which is odd.

Hence, there is only one number in the range $[8,11]$ which is fancy.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

3 Address Code - On site Hackathon - Finals

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Game Theory
• Math > Number Theory
• Math > Probablity