Bảo Bay Bổng đang học về các phép toán cộng, trừ, nhân, chia, do đó cô giáo có một trò chơi để thách đố bạn Bảo. Cô giáo đưa ra ba số nguyên dương ~a, b, c~. Sau đó, cô viết lên bảng ~y_1~ lần số ~x_1~, ~y_2~ lần số ~x_2~, ~\ldots~, ~y_n~ lần số ~x_n~.

Mỗi lượt, Bảo chọn ra một số ~p~ trên bảng và xoá số này đi, đồng thời nhân ~a~ với ~p~ hoặc nhân ~b~ với ~p~ (tức là ~a := a \times p~ hoặc ~b := b \times p~).

Cô giáo đố Bảo Bay Bổng làm cho tổng ~a + b~ chia hết cho ~c~ sau một số lượt chơi (có thể không cần lượt nào).

Bảo Bay Bổng chỉ mới học về các phép toán nên hiện đang cần sự trợ giúp của bạn. Hãy cho biết Bảo có thể hoàn thành thử thách mà cô giao với các thao tác đã cho không.

Bạn phải trả lời ~q~ truy vấn riêng biệt.

Dữ liệu

Dòng đầu chứa số nguyên dương ~q~ ~(1 \le q \le 5)~ — số truy vấn.

Trong mỗi truy vấn:

• Dòng đầu tiên chứa bốn số nguyên dương ~a, b, c, n~ ~(1 \le a, b, c \le 10^9;\ 1 \le n \le 4)~.

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x_i, y_i~ ~(1 \le x_i \le 10^9;\ 1 \le y_i \le 35)~.

Kết quả

• Với mỗi truy vấn, in ra YES nếu Bảo có thể hoàn thành thử thách hoặc NO nếu ngược lại.

Ví dụ

Sample Input

3
1 2 7 2
6 2
2 2
5 9 7 3
2 3
3 4
4 5
5 6 9 1
4 15

Sample Output

YES
YES
NO

Giải thích

• Trong truy vấn đầu tiên, Bảo có thể nhân ~a~ với 6 và nhân ~b~ với 2 hai lần. Khi đó ~1 \times 6 + 2 \times 2 \times 2 = 14~ chia hết cho 7.

• Trong truy vấn thứ hai, Bảo không cần làm gì vì ~a + b~ đã chia hết cho ~c~ ngay từ đầu.

• Trong truy vấn cuối cùng, Bảo không thể hoàn thành thử thách với các thao tác đã cho.

Chấm điểm

Đặt ~S = y_1 + y_2 + \ldots + y_n~.

• Subtask 1 (~50\%~ số test): ~1 \le S \le 15~.

• Subtask 2 (~50\%~ số test): ~1 \le S \le 35~.