十进制异或

题目描述

定义两个数的十进制按位异或运算 $\oplus$：设有 $a\oplus b=c$，且 $a,b,c$ 的十进制表示分别为 $\overline{\cdots a_{2}a_{1}a_{0}},\overline{\cdots b_{2}b_{1}b_{0}},\overline{\cdots c_{2}c_{1}c_{0}}$，则对于全部的 $i\in\mathbb{N}$ 有 $c_{i}=(a_{i}+b_{i})\bmod 10$。

给定三个整数 $L,R,K$，求出满足 $L\le x,y\le R$ 且 $x\oplus y=K$ 的有序对 $(x,y)$ 的数量。

输入

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

一行包含三个整数 $L$，$R$ 和 $K$，含义见题目描述。

保证所有的数据满足 $1\le T\le10000$。

保证所有的数据满足 $0\le L\le R\le10^{18}, 0\le K\le10^{18}$。

输出

对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为该组数据的答案。

输入样例

1
1 7 3

输出样例

Case #1: 4

样例解释

满足要求的 $(x,y)$ 对为：$(1,2),(2,1),(6,7),(7,6)$。