Левко очень любит различные множества.
У Левко есть два массива целых чисел a1, a2, ... , an и b1, b2, ... , bm и простое число p. Сегодня он генерирует n множеств. Опишем процесс генерации i-ого множества:
- Сначала в нем находится единственное число 1.
- Возьмем любой элемент c из этого множества. Для всех j (1 ≤ j ≤ m), если числа (c·aibj) mod p нет в этом множестве, то добавим его туда.
- Повторяем пункт 2 пока можем добавить хотя бы один элемент в наше множество.
Левко очень интересно сколько чисел принадлежат хотя бы одному множеству. Другими словами он хочет найти размер объединения n сгенерированных множеств.
Выходные данные
Единственное число — размер объединения множеств.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 7
2
5
|
3
|
|
2
|
1 2 7
2
2 4
|
3
|
|
3
|
2 1 7
1 6
2
|
1
|
|
4
|
2 1 7
1 6
5
|
2
|