题目背景

你听过三位一体结吗？三个空间用一个循环结连接在一起，不断闭环。

三个空间又指什么呢？循环结的维护者又是谁呢？

出生于主世界的玩家的虚拟体 Steve，应该内心已经有了答案。

题目描述

主世界可以观察地狱和末地，地狱和末地可以转化为两个长为 $n$ 的序列 $a_i,b_i$，称满足下面这个要求：

$$\gcd(a_l,a_{l+1},\cdots,a_r)=\text{lcm}(b_l,b_{l+1},\cdots,b_r) $$

的区间 $[l,r]$ 为相克区间。

Steve 是你的虚拟体，他问你：

• 最长的相克区间长度是多少？
• 一共有多少个相克区间？

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$ 代表序列长度。

第二行 $n$ 个整数代表序列 $a_i$。

第三行 $n$ 个整数代表序列 $b_i$。

输出格式

一行空格隔开的两个整数：

• 最长相克区间长度。
• 相克区间个数。

答案对 $998244353$ 取模。

5
18 10 8 4 12
2 2 2 2 2

5 7

说明/提示

样例 1 解释

满足要求的区间如下：

• $[1,2]$，长度为 $2$。
• $[1,3]$，长度为 $3$。
• $[2,3]$，长度为 $2$。
• $[1,4]$，长度为 $4$。
• $[2,4]$，长度为 $3$。
• $[1,5]$，长度为 $5$。
• $[2,5]$，长度为 $4$。

一共有 $7$ 个区间满足要求，最长的区间长度为 $5$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$n \le 10$。
• Subtask 2（20 pts）：$n \le 1000$。
• Subtask 3（30 pts）：$a_i,b_i \le 10$。
• Subtask 4（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i,b_i \le 1000$。