IGAME - Interesting Game

no tags 

Alice and Bob play an interesting game and the game is played on a number.

So a player, on his chance, can choose any non zero digit of the number and decrease the digit by any non zero amount such that the resulting digit remains non-negative. The player who gets all the digits of the number 0 wins. Both play optimally and Alice starts first. Now tell how many numbers are there between A and B on which if the game is played Alice wins and also find how many numbers are there where Bob wins. On every number between A and B, Alice plays first on that number.

Input

The input line consists of T test cases. On each line there are two numbers A and B.

Output

The output line consists of T lines each having two numbers.

Constraints

1 ≤ T ≤ 10000
1 ≤ A ≤ B ≤ 1018

Sample

Input:
2
1 10
101 110

Output:
10 0
8 2

Explanation

In the first case the first player Alice will always win because she can reduce any digit to 0.

In the second case the second player Bob will win on 2 numbers 101 and 110. Rest Alice will win.


hide comments
Oasis: 2015-02-09 17:01:39

time limit too strict..getting tle with fast i/o and O(n) algorithm

Raghav Aggiwal: 2014-10-20 07:42:31

finally! 'nim game+dp' and the rest is logic.. give it a try..

Vignesh Manoharan: 2014-09-24 22:20:47

does b-a go upto 10^18?

EDIT : Yes , B-A can be a large number of the order of 10^18.

Last edit: 2014-09-24 22:32:45

Added by:Aayush Agarwal
Date:2014-08-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for codecracker