AlgoLiga 2018

Jasio zainteresował się niedawno problemem generowania przez komputer liczb losowych. Dowiedział się, że tak naprawdę, programy zwane PRNG, generują tylko liczby, które wydają się losowe, gdyż są one wyliczane przy użyciu pewnych funkcji matematycznych. Jasiek spróbował więc samodzielnie stworzyć taki generator i wymyślił następującą funkcję:

a_i = |[(sin((i+a_i-1)·b/c))²·d/e]+f·a_i-1| mod |g|

gdzie:
sin(x) - sinus kąta x podanego w radianach;
[x] - największa liczba całkowita nie większa niż x;
|x| - wartość bezwzględna liczby x;
x mod y - reszta z dzielenia x przez y 

Następnie Jasio rozpoczął testy swojego generatora. Ustalał najpierw wartości parametrów b, c, d, e, f i g oraz liczby a₀ (będącej tzw. "ziarnem"), a następnie generował ciąg k liczb od a₁ do a_k. Chłopiec zauważył, że bardzo dużo zależy od przyjętych wartości parametrów. Czasami uzyskiwał ciąg liczb, które wydawały się losowe, a czasami pewne liczby pojawiały się o wiele częściej niż inne.

Ponieważ to dopiero pierwsze próby z generatorem liczb pseudolosowych, Jasiek nie ma wielkich wymagań. Uznaje, że generator działający według przyjętego zestawu parametrów jest dobry, jeśli w wygerowanym ciągu, żadna z liczb nie pojawia się częściej niż wszystkie pozostałe razem wzięte (czyli nie występuje na ponad połowie pozycji w ciągu). Chłopiec chce teraz intensywniej przebadać swoją funkcję. Potrzebny jest mu więc program, który automatycznie sprawdzi, czy przy danych parametrach generator jest wystarczająco dobry.

Wejście

W pierwszej linii liczba przypadków testowych t (1 ≤ t ≤ 10).
W każdej z kolejnych t linii najpierw liczba k (0 < k ≤ 2000000) oznaczająca ile liczb należy wygenerować, a następnie siedem liczb całkowitych: a₀, b, c, d, e, f, g (-10⁹ ≤ a₀, b, c, d, e, f, g ≤ 10⁹; c ≠ 0; e ≠ 0; g ≠ 0) - ziarno i parametry generatora.

Wyjście

Dla każdego przypadku testowego, w osobnej linii, napis "TAK", jeśli Jasio uzna generator za wystarczająco dobry. W przeciwnym wypadku napis "NIE", a po nim liczba, która wskazuje na to, że generator jest zły (czyli taka, która pojawiła się w wygenerowanym ciągu więcej niż k/2 razy).

Przykład

Wejście:
2
10 7 2 12 9 1 1 -4
10 0 1 2 5 3 -2 3

Wyjście:
NIE 3
TAK

Pomoc do przykładu: 
W pierwszym teście wygenerowane zostaną liczby: 3 3 1 1 3 3 3 3 2 1. Liczba 3 pojawia się 6 razy wśród 10 liczb.
W drugim teście wygenerowane zostaną liczby: 0 1 1 2 1 2 0 0 1 2. Tu żadna liczba nie występuje więcej niż 5 razy.