Problem Description

Given a sequence $f$ that satisfies $f_n = a_n f_{n-1} + b_n \ (n \ge 1)$.

Determine whether there exists a non-negative integer $f_0$ such that for all $1 \le i \le k$, $f_i$ is a multiple of the prime $p_i$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

For each test case:

• The first line contains an integer $k$.
• The second line contains $k$ integers $a_1, a_2, \dots, a_k$.
• The third line contains $k$ integers $b_1, b_2, \dots, b_k$.
• The fourth line contains $k$ integers $p_1, p_2, \dots, p_k$, and it is guaranteed that $p$ is prime.

Output Format

For each test case:

• Output one string per line. If there exists an $f_0$ that satisfies the conditions, output Yes; otherwise, output No.

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

Yes
No

Hint

[Sample 1 Explanation]

For the first test case, one feasible solution is $f_0 = 1$. In this case, $f_1 = 3, f_2 = 5, f_3 = 7$.

For the second test case, there is no $f_0$ that satisfies the conditions.

[Constraints and Notes]

This problem uses bundled tests.

• 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): no special constraints.

For $100\%$ of the testdata: $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$, and $p$ is prime.

Translated by ChatGPT 5