Description

Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:

1. Every even digit appears an even number of times in its decimal representation

2. Every odd digit appears an odd number of times in its decimal representation

For example, 7, 221, 6622 and 122344555667 are balanced numbers while 335511, 211, and 62 are not.

Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where both A and B are included.

Format

Input

The first line contains an integer T representing the number of test cases.

A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that $1 <= A <= B <= 1e19$

Output

For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval

Samples

2
1 1000
1 9

159
5