У Кодера ZS'а есть большое дерево. Его можно представить как неориентированный связный граф из n вершин, пронумерованных от 0 до n - 1, и n - 1 ребер между ними. На каждом ребре записана одна ненулевая цифра.
Однажды, Кодер ZS заскучал и решил исследовать некоторые параметры дерева. Он выбрал целое положительное M, которое является взаимно простым с 10, т.е. 
.
ZS считает упорядоченную пару различных вершин (u, v) интересной, когда если бы он проследовал по кратчайшему пути от вершины u до вершины v и выписывал цифры, которые он встречает на своем пути, в том же порядке, он получил бы десятичную запись целого числа, делящегося на M.
Формально, ZS считает упорядоченную пару различных вершин (u, v) интересной, если верно следующее:
- Пусть a1 = u, a2, ..., ak = v — последовательность вершин на кратчайшем пути от u до v в порядке их встречи;
- Пусть di (1 ≤ i < k) — цифра, записанная на ребре между вершинами ai и ai + 1;
- Целое число
делится на M.
Помогите Кодеру ZS'у найти количество интересных пар!
Выходные данные
Выведите единственное целое число — количество интересных (по мнению Кодера ZS'а) пар.
Примечание
В первом примере из условия интересными являются пары (0, 4), (1, 2), (1, 5), (3, 2), (2, 5), (5, 2), (3, 5). Числа, образуемые этими парами — 14, 21, 217, 91, 7, 7, 917 соответственно, все они кратны 7. Заметьте, что (2, 5) и (5, 2) считаются различными.
Во втором примере из условия интересными являются пары (4, 0), (0, 4), (3, 2), (2, 3), (0, 1), (1, 0), (4, 1), (1, 4), и 6 из этих пар дают число 33, а 2 из них дают число 3333, и все они кратны 11.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 7
0 1 2
4 2 4
2 0 1
3 0 9
2 5 7
|
7
|
|
2
|
5 11
1 2 3
2 0 3
3 0 3
4 3 3
|
8
|