小俊很喜欢数学,现在他要给你出一道严肃的数学题。 定义 $F[x]$ 为x在十进制表示下各位数字的异或和,例如$F(1234) \ = \ 1 \ xor \ 2 \ xor \ 3 \ xor \ 4 \ = \ 4$。给你两个数 $a, b(a \leq b)$。 求$F[a] \ + \ F[a+1] \ + \ F[ a+2]+ \ldots + \ F[ b-2] \ + \ F[ b-1] \ + \ F[b]$ 模 $10^9+7$ 的值 。
第一行一个$T$,表示有$T$组数据$( T < 26 )$。 每组数据第一行一个数$a$, 第二行一个数$b$,无多余空格。保证$|a|, |b|$不超过$100001$,$|a|$ 表示$a$的输入位数长度。
按输入顺序输出。 第$i$组数据格式Case #i: ans
4 0 1 2 2 1 10 9999 99999
Case #1: 1 Case #2: 2 Case #3: 46 Case #4: 649032