题号：NC243338
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
妈妈发现小竹逃走了，非常的气愤，她决定出去寻找小竹！和小竹不同的是，妈妈是道路上行走。
妈妈和小竹所在的城市有
个路口，
条道路，并且保证任意两个路口互相联通。每个路口根据妈妈审美的不同都有一个优雅值，而如果两个相邻的路口的优雅值存在至少两个共同的质因子
和
（
）则这两个相邻的路口就是共同优雅的。
妈妈将共同优雅联通块定义为：在城市中选取若干个路口，若这些路口们两两互相联通，且每两个相邻的路口都是共同优雅的，则该联通块称为共同优雅联通块。
注意：单独的一个路口也符合共同优雅联通块的定义。
妈妈想知道，整个城市的最大优雅联通块包含多少个路口。
妈妈和小竹所在的城市有
妈妈将共同优雅联通块定义为：在城市中选取若干个路口，若这些路口们两两互相联通，且每两个相邻的路口都是共同优雅的，则该联通块称为共同优雅联通块。
注意：单独的一个路口也符合共同优雅联通块的定义。
妈妈想知道，整个城市的最大优雅联通块包含多少个路口。
输入描述:
第一行一个正整数表示有
第二行个整数为
表示该路口的优雅值。
接下来,
表示
路口有一条道路。
输出描述:
一行一个整数，表示最大优雅联通块包含多少个路口。