Cryptographically Strong Keys

Time limit2sMemory limit256 MB

Summary

Given numbers a_i, the closure under gcd and lcm defines a set S; decide whether a query value v lies in S.

Level: Hard8 of 10
Topics: Number theory, Math, Greedy, Hash map
Solved: No attempts yet

Problem

Pasha has created his own data encryption protocol. In this protocol, the key used for encryption must belong to the set $S$ of cryptographically strong keys, which is built from a set of numbers $a_1, a_2, \ldots, a_n$ .

The set $S$ is the inclusion-minimal set with the following two properties:

Every number $a_1, a_2, \ldots, a_n$ belongs to $S$ .
If $x$ and $y$ belong to $S$ , then their greatest common divisor and their least common multiple also belong to $S$ .

Pasha wants to use the number $v$ as the key. Determine whether $v$ belongs to the set of cryptographically strong keys.

Input

The first line contains a positive integer $T$ , the number of test cases in the input. $T$ does not exceed 5. The descriptions of the test cases follow.

Each test case consists of three lines. The first line contains a positive integer $n$ ( $1 \le n \le 50\,000$ ). The second line contains $n$ numbers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^{12}$ ). The third line contains the number $v$ ( $1 \le v \le 10^{12}$ ) whose membership in the set of cryptographically strong keys must be checked.

Output

For each of the $T$ test cases, output YES on a separate line if $v$ belongs to the set of cryptographically strong keys, and NO otherwise.

Examples1

Example 1
Input
```
2
2
45 75
15
2
45 75
9
```
Expected output
```
YES
NO
```