SOLVE

LATER

Fancy That!

/

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}\)

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

Initializing Code Editor...