시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.000%

문제

Паша создал свой собственный протокол шифрования данных. Известно, что в этом протоколе ключ, используемый для шифрования, должен принадлежать множеству S криптостойких ключей, построенному по набору чисел a1a2, ..., an.

Множество S представляет собой минимальное по включению множество, которое обладает следующими двумя свойствами:

  1. Все числа a1a2, ..., an принадлежат S
  2. Если x и у принадлежат S, то их наибольший общий делитель и их наименьшее общее кратное также принадлежат S.

В качестве ключа Паша хочет использовать число v. Помогите Паше выяснить, принадлежит ли v множеству криптостойких ключей.

입력

Первая строка содержит целое положительное число T — число тестовых примеров во входных данных. Гарантируется, что T не превышает 5. Далее следуют описания тестовых примеров.

Каждый тестовый пример описывается тремя строками. В первой строке содержится целое положительное число n (1 ≤ n ≤ 50 000). Во второй строке находятся n чисел a1a2, ..., an (1 ≤ ai ≤ 1012). В третьей строке находится число v (1 ≤ v≤ 1012), принадлежность которого множеству криптостойких ключей необходимо проверить.

출력

Для каждого из T тестовых примеров в отдельной строке выведите YES, если v принадлежит множеству криптостойких номеров, и NO в противном случае.

예제 입력 1

2
2
45 75
15
2
45 75
9

예제 출력 1

YES
NO