对，Hang这学期整整挂了3科，居然连数据挖掘这种专业课都挂了，不愧是一天学一科的男人
这一天，Hang无聊一不小心就写了一只爬虫，爬了一堆每行4个整数的数据，Hang发现，这些数据是一个区间，和两个非负数，无聊的Hang想知道，在这个区间中有多少数满足在k进制下末尾正好有m个0
第一行包含一个整数 T (1≤T≤10 5 ) 表示数据组数。
对于每组数据包含一行，四个整数 l,r,k,m ( 0≤l≤r≤10 18, 2≤k≤16,0≤m≤100 )，含义如题目所述。
对于每组数据输出一行，包含一个整数，表示答案。
2 1 10 2 3 1 100 2 3
1 6