Eulers Peculiar Dream

After discovering the famous totient function $\phi(x)$ Euler got so fond of it that he applied it to every number he could find on his table. He played all day with this newly discovered function. Then he went to sleep. He was dreaming about the function too.

In the dream, he found a very big number $x$. Since he was playing with totient function he immediately applied totient function to $x$ and got a new number $\phi(x)$. But the number was still very large so he again applied totient to it and got another number $\phi(\phi(x))$ which was still way too big. As a result, Euler got frustrated. He wondered how many times he had to apply totient function before reaching $1$. Euler solved it in the dream. Can you do it too?

Formally, let $y_0 = x$

and $y_n = \phi(y_{n-1})$ where $n$ is an integer and $n\ge 1$

Find smallest $n$ such that $y_n = 1$

Note: Euler totient function of a positive integer $n$ is defined as the number of positive integers $i$ less than or equal to $n$ such that $gcd(n,i) = 1$

Input

First line of input contains an integer $k ( 1\le k \le 10^5)$

Next line contains $k$ prime numbers $p_1, p_2, … p_k$

Next line contains $k$ integers $e_1,e_2,…e_k$

For each $1\le i\le k$ , $2 \le p_i \le 10^6$

It is guaranteed that each $p_i$ is pairwise distinct.

For each $1\le i\le k$ , $1 \le e_i \le 10^6$

Then the input number is calculated as $x =\prod_{i = 1}^{k}p_i^{e_i}$

Output

Print the smallest positive $n$ such that $y_n = 1$

Since $n$ can be very large, output it modulo $998244353$

Samples

Input	Output
2 3 2 1 1	2

Input	Output
1 11 1	4