## UMNOZAK - Umnozak

The digit-product of a positive integer is the product of the number's decimal digits. For example, the digit-product of 2612 is 2 · 6 · 1 · 2 = 24.

The self-product of a number is the product of the number and its digit-product. For example, the self-product of 2612 is 2612 · 24 = 62688.

Write a program that, given two positive integers A and B (1 ≤ A ≤ B < 10^{18}), calculates the number of positive integers whose self-product is between A and B, inclusive.

### Input

The first line of input contains the integer T (1 ≤ T ≤ 20). The next T lines each contain a pair of integers A and B.

### Output

For each test case, print a line with the number of positive integers whose self-product is between A and B.

### Example

Input:3 20 30 145 192 2224222 2224222Output:2 4 1

For the second example, the self-products of the numbers 19, 24, 32, and 41 are 171, 192, 192 and 164, respectively.

Added by: | Neal Wu |

Date: | 2008-11-08 |

Time limit: | 1.329s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO |

Resource: | Croatian Olympiad in Informatics 2008 |