AlgoLiga 2018

Król Bajtolomeusz ogłosił niedawno konkurs na projekt nowej fontanny, która miałaby upiększyć centralny punkt nowego ogrodu. Spośród wielu pomysłów, władcy najbardziej spodobał się projekt pod tytułem "Fontanna binarna". Budowa rozpoczęła się szybko i przebiega bez przeszkód. Skutek jest więc taki, że już niedługo ogród ozdobi nowa budowla o bardzo ciekawej konstrukcji.

Fontanna ma N poziomów, na których znajdują się misy. Na pierwszym poziomie od góry, znajduje się misa nr 1 o pojemności p₁ litrów i to do niej doprowadzana jest woda z basenu z szybkością 1 litra na sekundę. Kiedy misa nr 1 wypełni się, woda przelewa się z niej do mis nr 2 i 3 znajdujących się na drugim od góry poziomie. Oczywiście misy te wypełniają się dwa razy wolniej niż misa nr 1, bo do każdej dopływa pół litra wody na sekundę. Po napełnieniu, woda z misy nr 2 zaczyna się przelewać do mis 4 i 5, a z misy nr 3 do mis 6 i 7. Kolejne poziomy mają analogiczną konstrukcję.

Cała fontanna składa się więc z 2^N-1 mis. Na i-tym od góry poziomie znajdują się misy o numerach od 2^i-1 do 2ⁱ-1. Po napełnieniu misy nr m woda przelewa się z niej równomiernie do mis nr 2m i 2m+1. Misy na poziomie i+1 napełniają się z szybkością dwa razy mniejszą niż te na poziomie i. Z mis znajdujących się na najniższym poziomie woda przelewa się do basenu znajdującego się u podstawy fontanny.

O tym, że to właśnie ten projekt został wybrany przez króla do realizacji, zdecydowała między innymi ciekawa zasada założona przez konstruktora. Pojemność poszczególnych mis nie jest jednakowa, lecz wyznaczana według następującego wzoru:

p_m = ((m^a+m) mod b) + c

gdzie: 
p_m - pojemność misy numer m (w litrach)
x mod y - reszta z dzielenia x przez y 
a,b,c - ustalone współczynniki konstrukcyjne 

Bajtolomeusza ciekawi już tylko jedno. Jak długo trzeba będzie czekać na napełnienie wszystkich mis, pustej początkowo fontanny?

Wejście

W pierwszej linii liczba przypadków testowych t (1 ≤ t ≤ 5).
W każdej z kolejnych t linii najpierw liczba N (2 ≤ N ≤ 22) oznaczająca liczbę poziomów fontanny, a następnie trzy liczby całkowite: a, b, c (2 ≤ a, b, c ≤ 22222) - współczynniki konstrukcyjne fontanny.

Wyjście

Dla każdego przypadku testowego, w osobnej linii, liczba sekund potrzebnych do napełnienia wszystkich mis fontanny.

Przykład

Wejście:
2
3 3 6 2
2 2 2 2

Wyjście:
40
6

Pomoc do przykładu: 
W pierwszym teście kolejne misy będą miały pojemność: 4 6 2 4 6 2 4.