가스

서로 다른 액체 시약이 담긴 시험관 $n$개 $t_1, t_2, \dots, t_n$가 있고, 비커에는 또 다른 시약 $C$가 $M$ mg 들어 있습니다.

시험관 $t_i$에 시약 $C$를 $x_i$ mg 넣으면 가스 $G$가 발생합니다. 발생하는 가스의 양은 일차 함수 $f_i(x_i) = a_i \cdot x_i + b_i$ (단위: mg)로 정해집니다. 시약 $C$는 정수 단위로만 넣을 수 있으므로, 모든 $x_i$는 음이 아닌 정수여야 합니다.

예를 들어 $f_3(x) = 3 \cdot x + 2$일 때 $t_3$에 $C$를 $x = 40$ mg 넣으면 $3 \cdot 40 + 2 = 122$ mg의 가스가 발생합니다.

$C$ $M$ mg 전부를 시험관들에 나누어 넣어서 모든 시험관에서 발생하는 가스의 양을 같게 만들어야 합니다. 즉, $x_1 + x_2 + \dots + x_n = M$이면서 $f_1(x_1) = f_2(x_2) = \dots = f_n(x_n)$을 만족하는 음이 아닌 정수 $x_1, x_2, \dots, x_n$을 골라야 합니다.

예를 들어 함수가 $f_1(x) = 3 \cdot x + 5$, $f_2(x) = 4 \cdot x + 3$, $f_3(x) = 1 \cdot x + 7$인 시험관 3개와 $M = 27$이 주어지면, $x_1 = 6$, $x_2 = 5$, $x_3 = 16$을 골라 모든 시험관에서 $23$ mg의 가스를 발생시킬 수 있습니다. 반면 $M = 26$이면 각 시험관의 가스 양을 같게 만드는 것이 불가능합니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스는 다음과 같이 주어집니다. 첫 줄에 시험관의 수를 나타내는 정수 $n$ ($1 \le n < 20$)이 주어집니다. 이어서 시험관 순서대로 $a_i$와 $b_i$를 나타내는 정수 쌍 $n$개가 주어지며, $1 \le a_i \le 10$, $1 \le b_i \le 1000$입니다. 각 정수는 공백으로 구분되고, 각 쌍은 여러 줄에 나뉘어 있거나 한 줄에 함께 있을 수 있습니다. 테스트 케이스의 마지막 줄에는 $M$이 주어지며, $M$은 $10000$보다 작은 양의 정수입니다.

각 테스트 케이스마다 정확히 한 줄을 출력합니다. 모든 시험관의 가스 양을 같게 만들 수 있으면, 각 시험관에서 발생하는 공통 가스 양 $G$를 출력합니다. 불가능하면 $0$을 출력합니다.