AlgoLiga 2018

Właśnie obliczyliśmy, że suma przeznaczona przez sponsorów na nagrody w tej edycji AlgoLigi wynosi równo p₁^w₁×p₂^w₂×p₃^w₃×...p_n^w_n groszy. Zastanawiamy się czy tę kwotę da się równo podzielić na m osób?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 100) określająca liczbę zestawów danych. W kolejnych liniach znajduje się t zestawów danych.

Każdy zestaw danych składa się z dwóch linii w pierwszej linii znajdują się liczby n i m (1 ≤ n ≤ 100; 1 ≤ m ≤ 10⁹) oznaczające odpowiednio liczbę czynników iloczynu kwoty przeznaczonej na nagrody oraz liczbę nagrodzonych. W drugiej linii znajduje się n par liczb całkowitych p, w (1 ≤ p, w ≤ 10⁹) określających podstawę i wykładnik każdego z czynników.

Wyjście

Na wyjściu dla każdego zestawu danych należy wypisać TAK jeżeli podaną kwotę da się równo podzielić na m osób albo NIE w przeciwnym wypadku.

Przykład

Wejście

4
3 7
2 3 3 2 5 2
3 10
2 3 3 2 5 2
4 9220
3 3 2 2 6 2 4 3
4 82944
3 3 2 2 6 2 4 3

Wyjście

NIE
TAK
NIE
TAK