题目描述

已知数列 $f$ 满足 $f_n=a_nf_{n-1}+b_n\ (n\ge 1)$。

问是否存在非负整数 $f_0$，使得 $\forall 1\le i\le k$，$f_i$ 为质数 $p_i$ 的倍数。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行一个整数 $k$。
• 第二行 $k$ 个整数 $a_1,a_2,\dots,a_k$。
• 第三行 $k$ 个整数 $b_1,b_2,\dots,b_k$。
• 第四行 $k$ 个整数 $p_1,p_2,\dots,p_k$，保证 $p$ 为质数。

输出格式

对于每组测试数据：

• 一行一个字符串，若存在满足条件的 $f_0$ 则输出 Yes，否则输出 No。

2
3
1 1 1
2 2 2
3 5 7
3
1 1 1
2 2 2
3 3 3

Yes
No

提示

【样例 1 解释】

对于第一组测试数据，一个可行的解为 $f_0=1$，此时 $f_1=3,f_2=5,f_3=7$。

对于第二组测试数据，没有满足条件的 $f_0$。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（10 points）：$k=1$。
• Subtask 2（20 points）：$k\le 2$。
• Subtask 3（20 points）：$k\le 5$，$p_i\le 20$。
• Subtask 4（50 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le k\le 10^3$，$0\le a_i,b_i\le 10^9$，$2\le p_i\le 10^9$，$p$ 为质数。