Gra w dzielniki

Limit pamięci: 256 MB

Jak zapewne wszyscy pamiętają, Bajtuś i Bituś to dwaj chłopcy, którzy lubią grać w rozmaite gry. Ostatnio Bituś poniósł porażkę, zjadając oznaczony kawałek czekolady i chce się zrewanżować Bajtusiowi. Zaproponował mu nową grę, jej zasady są następujące.

Początkowo na tablicy napisana jest pewna liczba całkowita większa od . Gracze na przemian zastępują liczbę aktualnie napisaną na tablicy jej wybranym dzielnikiem (różnym od niej samej). Gdy któryś z graczy napisze liczbę , gra się kończy. Dla każdego dzielnika liczby , z wyjątkiem , określone są dwie liczby i . Gdy Bajtuś w trakcie gry napisze na tablicy liczbę , dostaje punktów. Z kolei Bituś, za napisanie otrzymuje punktów. Celem gry jest zmaksymalizowanie przewagi nad przeciwnikiem, czyli różnicy między zdobytymi punktami a punktami przeciwnika.

Bituś wybrał już liczbę oraz punktację dla jej dzielników. Za to Bajtuś może wybrać, który z chłopców wykona pierwszy ruch. Chciałby on wobec tego wiedzieć, ile w obydwu przypadkach wyniesie przewaga rozpoczynającego grę, przy założeniu, że obaj chłopcy grają optymalnie.

Wejście

Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą oznaczającą liczbę przypadków testowych, które są kolejno opisane w dalszej części wejścia. Opis jednego przypadku testowego rozpoczyna się wierszem z czterema liczbami całkowitymi i (, ). Iloczyn jest równy liczbie , która początkowo znajduje się na tablicy, zaś oznacza liczbę dodatnich dzielników liczby .

W dalszych wierszach znajduje się punktacja dla kolejnych (różnych od ) dzielników , w kolejności rosnącej. W -tym z tych wierszy znajdują się dwie liczby całkowite oraz (), które oznaczają liczbę punktów przyznawanych odpowiednio Bajtusiowi i Bitusiowi za napisanie na tablicy liczby , czyli -tego dzielnika .

Suma liczb po wszystkich przypadkach testowych w jednym pliku nie przekracza .

Wyjście

Wypisz wierszy z odpowiedziami dla poszczególnych przypadków testowych. Odpowiedź dla jednego przypadku składa się z dwóch liczb całkowitych i , które oznaczają przewagę rozpoczynającego grę, jeśli jest nim, odpowiednio, Bajtuś i Bituś.

Przykład

Dla danych wejściowych:

2
7 1 1 2
3 1
2 2 1 3
1 1
3 3

poprawną odpowiedzią jest:

3 1
2 2

Wyjaśnienie: W pierwszym przypadku testowym rozpoczynający grę może napisać jedynie , co od razu kończy grę. W drugim zaś opłaca się napisać i pozwolić przeciwnikowi napisać .

Autor zadania: Tomasz Kociumaka.