题解

题面描述

给定区间 $[l,\;r]$ 和两个数字 $x$ 与 $k$，数字 $num$ 如果其各个位上的数字中 $x$ 恰好出现 $k$ 次，则称 $num$ 为“小美的幸运数字”。
题目要求计算在区间 $[l,\;r]$ 中有多少个幸运数字。

思路

题目内容

小美认为一个数字$num$,如果其数位上的数字$x$恰好出现$k$次，那么认为$num$是她的幸运数字，请你帮助小美计算在$1$至$r$有多少个幸运数字。

输入描述

第一行一个整数$t(1≤t≤10^4)$,表示数据组数，对于每组数据格式为:

每行四个整数$l,r,x,k(1≤l≤r≤10^{12},0≤x≤9,1≤k≤12)$。

输出描述

对于每组数据输出一个整数，表示当前询问下的幸运数字个数。

样例1

输入

3
1 20 1 1
1 20 1 2
114514 5201314 5 2

输出

10
1 
550093