Migrated from Lutece 1808 琪露诺的算术教室

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

琪露诺是个聪明的精灵，她非常擅长和数字有关的游戏
直到有一天灵梦进入了迷雾深林，她遇见了琪露诺，并向她提出了一个问题
给定$n,a,b,d$，统计$\underbrace{aaa~\cdots~aaa}_{n个a}~\times~b$的结果里有多少个数字$d$

Input

多组测试数据
第一行有一个整数$T$，表示测试数据的数目($1≤T≤10^5$)
接下来$T$行，每一行表示一组测试数据，有四个整数$a,b,d,n$（$1 \le a,b\le 9,0\le d \le 9,1 \le n \le 10^9$）

Output

输出$T$行表示答案

Samples

2
3 3 9 10
3 3 0 10

10
0

Note

$3333333333*3=9999999999$里面有$10$个$9$

Resources

第九届ACM趣味程序设计竞赛第三场（正式赛）