We have n test tubes {t} containing different liquid chemicals. And we have M mg(milligram) of another i chemical C in a beaker. If we put x mg of Cinto a test tube ti, then G (a sort of gas) is produced in ti. The amount of G produced in each t is determined by a linear tube function f(xi) = ai * xi + bi (unit is mg), where xi is the amount of C put into ti. Note that we can only measure integer amount of C, and so every xi should be an integer.
Assume that f3(x) = 3 * x+ 2 for test tube t3. If we put x=40 mg of C into t3 , then 122 mg of G is produced. This experiment has a requirement, that is, we must equalize the amount of G produced in every ti by carefully distributing Mover all n tubes, that is x1 + x2 + ... + xn= M.
For example, if we have only three test tubes with tube functions f1(x) = 3 * x + 5 , f2(x) = 4 * x + 3 , f3(x) = 1 * x + 7 and M= 27, then we can make 23 mg of G in each tube by assigning x1 = 6, x2 = 5, x3 = 16. But it is impossible to equalize the amount of G produced in each tube if we are given M = 26.
Input
Your program is to read from standard input. The input consists of Ttest cases. The number of test cases T is given in the first line of the input. Each testcase starts with a line containing an integer n < 20, the number of integer pairs, ai and bi. A pair of two integers, ai and bi , is given in the following n lines. And finally M, the initial amount of C is given in the next line. There is at least a single space between aiand bi, where 1 <= ai <= 10 and 1 <= bi <= 1,000. And M is a positive integer less than 10,000.
Output
Your program is to write to standard output. Print exactly one line for each test case. Print the amount of G produced in each tube, if it is possible to equalize the amount of in each tube. Print 0, if it is impossible to equalize the amount of G in each tube.
Sample Input
3
3
3 5 4 3 1 7
27
3
3 5 4 3 1 7
26
8
2 156 2 2 2 216 4 12 3 24 5 36 1 96 3 6
695
Sample Output
23
0
276
