E - Koła zębate
Twoja mała siostra dostała nowy zestaw młodego konstruktora, który zawiera wiele kół zębatych różnych rozmiarów. Teraz zaczyna budować układy z rożnymi przełożeniami. Szybko jednak spostrzega, że niektóre przełożenia są bardzo ciężkie do zrealizowania, a jeszcze inne nie mogą być nigdy osiągnięte. Chciałaby mieć program, który powiedziałby jej, które przełożenia są osiągalne, a które nie. O napisanie takiego programu poprosiła Ciebie.
Jako przykład rozpatrzmy zestaw składający się z trzech rodzajów kół zębatych o liczbie zębów 6, 12 i 30. Twoja siostra chce zrealizować przełożenie o stosunku 5 : 4. Jedna z możliwości jest pokazana na rysunku 1.
Rys 1. Przykładowe zębatki.
Jest to kompletny układ realizujący przełożenie 5 : 4. Użyte są cztery koła: o rozmiarach 30 i 12 na pierwszej osi i o rozmiarach 6 i 12 na drugiej osi. Przełożenie wynosi:
Z podanych kół jednak nie można złożyć przełożenia 1 : 6.
Zadanie
Mając dane rozmiary kół zębatych (ilość zębów, które posiadają) sprawdź czy zadane przełożenie jest osiągalne. Masz do dyspozycji skończoną liczbę każdego z kół zębatych.
Wejście
W pierwszej linii podana jest liczba testów. Dla każdego testu podana jest najpierw liczba kół zębatych w zestawie n(1 ≤ n ≤ 20). W kolejnej linii znajduje się n liczb: c1, c2, ..., cn (5 ≤ ci ≤ 100 dla i = 1, 2, ..., n). Oznaczają one n różnych rozmiarów kół zębatych w zestawie. Wiadomo, że istnieje koło zębate o minimalnym rozmiarze cmin = min{c1, c2, ..., cn}, takie że każde koło c1, c2, ..., cn jest wielokrotnością cmin. W kolejnej linii podana jest liczba m przekładni, które musisz sprawdzić. W kolejnych m liniach podane są dwie liczby a i b (1 ≤ a, b ≤ 10000). Oznaczają one przekładnie o stosunku a : b.
Wyjście
Dla każdej przekładni wypisz jedną linię zawierającą "TAK" jeżeli przekładnia może zostać zrealizowana. Jeżeli nie można osiągnąć takiej przekładni, to wypisz "NIE". Po każdym z testów wypisz jedną pustą linie.
Przykładowe wejście
2
3
6 12 30
2
5 4
1 6
1
42
2
13 13
42 1
Przykładowe wyjście
TAK
NIE
TAK
NIE