시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 NM oraz A ( 1 <= <= 1000 , 1<= M <= 1018 , 0 <= <= 1018). W następnych N liniach znajdują się kolejne komendy programu (  1 <= X <= 1018 ). 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.

예제 입력 1

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

예제 출력 1

3
0