8831번 - Program 다국어

Hektor ostatnio zaczął uczyć się języka programowania C--. Programy w tym języku operują na jednej zmiennej naturalnej umieszczonej w pamięci przed wykonaniem jakichkolwiek komend.

W C-- dozwolone są następujące komendy:

• += X ( komenda dodaje liczbę X do zmiennej w pamięci )
• -= X ( analogicznie odejmuje liczbę X od zmiennej w pamięci )
• *= X ( analogicznie mnoży zmienną w pamięci przez X )
• /= X ( analogicznie dzieli zmienną w pamięci przez X )

Hektor napisał program w C-- i chciałby, żeby po jego wykonaniu wartość zmiennej w pamięci wynosiła A. Ile jest wartości początkowych z przedziału [1,M], które na to pozwalają?

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).

Pierwsza linia pojedynczego zestawu testowego zawiera liczby całkowite N, M oraz A ( 1 <= N <= 1000 , 1<= M <= 10¹⁸ , 0 <= A <= 10¹⁸). W następnych N liniach znajdują się kolejne komendy programu (  1 <= X <= 10¹⁸ ). Możesz założyć, że po wykonaniu każdej komendy liczba na której operuje program zmieści się w (signed) long long i będzie nieujemna.

Dla każdego zestawu wypisz ile jest opisanych w treści wartości początkowych.