P16507 [GKS 2015 #B] gWheels

一辆典型的山地自行车有两组齿轮：一组连接到脚踏，另一组连接到后轮。一组齿轮由多个通常具有不同齿数的齿轮组成。一条链条将脚踏齿轮组中的一个齿轮与车轮齿轮组中的一个齿轮连接起来，这决定了骑车人的踩踏速度与车轮速度之间的比率。例如，如果链条将脚踏上一个有 $5$ 个齿的齿轮与车轮上一个有 $10$ 个齿的齿轮连接起来，比率将是 $1/2$，因为骑车人需要让脚踏齿轮旋转两圈才能使车轮旋转一圈。骑车人可以变换链条，将脚踏组中的任意一个齿轮与车轮组中的任意一个齿轮连接起来。 你刚刚购买了一辆特殊的新型山地自行车，它带有**三个**齿轮组：一个连接到脚踏，一个连接到车轮，以及一个额外的中间齿轮组。这辆山地车有两条链条；第一条链条必须始终将脚踏齿轮组中的一个齿轮与额外齿轮组中的一个齿轮连接起来，第二条链条必须始终将额外齿轮组中的一个齿轮与车轮齿轮组中的一个齿轮连接起来。此外，两条链条不能同时使用额外齿轮组中的同一个齿轮。 给定脚踏、额外以及车轮齿轮组中可用齿轮的齿数，是否有可能使比率（踩踏速度与车轮速度之比）恰好为 $P/Q$ ？对于给定的一组齿轮，你可能需要回答多个此类问题。

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一行包含 $3$ 个整数 $N_p$、$N_e$ 和 $N_t$ 开始，分别表示脚踏、额外以及车轮齿轮组中齿轮的数量。接着，还有三行。这三行分别包含 $N_p$、$N_e$ 和 $N_t$ 个整数，依次表示脚踏、额外以及车轮齿轮组中不同齿轮的齿数。（数据保证同一齿轮组内各齿轮的齿数互不相同。）在此之后的一行包含一个整数 $M$，表示问题的数量。最后，有 $M$ 行，每行包含两个整数 $P$ 和 $Q$，表示目标比率。（数据不保证该比率为既约分数。）

对于每个测试用例，首先输出一行形如 `Case #x:` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后按照问题给出的顺序，为该测试用例中的每个问题输出一行：若有可能使比率达到 $P/Q$，则输出 `Yes`，若不可能，则输出 `No`。

对于该测试用例中的第一个问题，由于两条链条必须使用额外齿轮组中的不同齿轮，而要求比率为 $1/1$ 会迫使两条链条使用额外齿轮组中的同一个齿轮，这是不允许的，因此无法得到比率 $1/1$。 对于该测试用例中的第二个问题，你可以将第一条链条连接脚踏齿轮组中 $5$ 齿的齿轮与额外齿轮组中 $4$ 齿的齿轮，并将第二条链条连接额外齿轮组中 $6$ 齿的齿轮与车轮齿轮组中 $3$ 齿的齿轮。通过此配置，得到的比率为 $5/2$。 ### 限制 $1 \le T \le 100$。 $1 \le$ 每个齿轮的齿数 $\le 10000$。 $1 \le$ 所有 $P$、$Q$ 的值 $\le 10^9$。 $1 \le M \le 10$。 **小数据集（测试集 1 - 可见）** $1 \le N_p, N_t \le 10$。 $2 \le N_e \le 10$。 **大数据集（测试集 2 - 隐藏）** $1 \le N_p, N_t \le 2000$。 $2 \le N_e \le 2000$。 翻译由 DeepSeek V4 Pro 完成