Problem C. Yukikaze and Demons
时间限制 1 ms
内存限制 128 MB
Yukikaze is facing a huge crisis!
Under the attack of a kind of demons, dragon eaters, the dragon forest is endanger. As a member of the Biscotti Knights Secret Squad, she must do something to save the dragon forest.
The road in the dragon forest forms an undirected tree. Every vertex is occupied by a demon with a type denoted by a decimal digit.
In one of her strike, she can sweep out all the enemy on the path if and only if the decimal number formed by concatenating the types of enemy on the path sequentially is divisible by a special number $k$.
The demons are destroying the forest! Time is limited, she needs to know how many path in the dragon forest can be cleared in a single strike of hers.
In this problem, a single vertex is considered as a path too!
输入数据
输出数据
For each test case, print the answer in a line.
样例输入
复制
2
4 3 0123
1 2
1 4
3 1
2 10 50
1 2
样例输出
样例说明
In the first example, there are 6 path can be cleared in a single strike: $1,1-4,2-1-3,3-1-2,4,4-1$
$ Mathjax font initiator $