Levko非常喜欢各种套装。
Levko 有两个整数数组 a1, a2, ... , an 和 b1, b2, ... , bm 和一个素数 p。今天他生成了 n 组。我们来描述一下第i个集合的生成过程:
1. 首先它有一个数字 1。
2. 让我们从该集合中取出任意元素 c。对于所有 j (1 ≤ j ≤ m),如果数字 (c·aibj) mod p 没有出现在集合中,则将其添加到集合中。
3. 重复步骤 2,只要我们可以向集合中添加至少一个元素即可。
Levko 想知道,有多少个数字属于至少一组。也就是说,他想知道n个生成集的并集有多大。
输入
第一行包含三个整数 n、m 和 p (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 2 ≤ p ≤ 109),p 是质数。
第二行包含空格分隔的整数 a1, a2, ... , an (1 ≤ ai < p)。第三行包含空格分隔的整数 b1, b2, ... , bm (1 ≤ bi ≤ 109)。
输出
单个数字 — 集合并集的大小。
示例
输入 #1
1 1 7 2 5
输出 #1
3
输入 #2
1 2 7 2 2 4
输出 #2
3
输入 #3
2 1 7 1 6 2
输出 #3
1
输入#4
2 1 7 1 6 5
输出#4
2