C-- 프로그램

헥토르는 최근에 프로그래밍 언어 C--를 배우기 시작했습니다. 이 언어의 프로그램은 명령을 실행하기 전에 메모리에 저장된 하나의 자연수 변수를 대상으로 동작합니다.

C--에서는 다음 명령을 사용할 수 있습니다.

• += X : 메모리의 변수에 $X$를 더합니다.
• -= X : 메모리의 변수에서 $X$를 뺍니다.
• *= X : 메모리의 변수에 $X$를 곱합니다.
• /= X : 메모리의 변수를 $X$로 나눕니다. 나눗셈은 몫만 취하는 정수 나눗셈(내림)입니다.

헥토르는 C-- 프로그램을 작성했고, 실행이 끝난 뒤 메모리 변수의 값이 $A$가 되기를 원합니다. 구간 $[1, M]$ 안의 초기값 중에서 이를 만족시키는 값은 몇 개입니까?

첫째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 10$)가 주어집니다.

각 테스트 케이스의 첫째 줄에는 정수 $N$, $M$, $A$ ($1 \le N \le 1000$, $1 \le M \le 10^{18}$, $0 \le A \le 10^{18}$)가 주어집니다. 이어지는 $N$개의 줄에는 프로그램의 명령이 순서대로 주어지며, 각 명령의 $X$는 $1 \le X \le 10^{18}$을 만족합니다.

각 명령을 실행한 뒤의 변수 값은 항상 부호 있는 64비트 정수(signed long long) 범위에 들어가며 음수가 되지 않는다고 가정해도 됩니다.

각 테스트 케이스마다 문제의 조건을 만족하는 초기값의 개수를 한 줄에 하나씩 출력합니다.