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.</p>

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 ).</p>

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.

예제 입력

2
1 6 1
/= 3
2 10 4
+= 2
*= 3

예제 출력

3
0