Bisection method is a very basic and robust numerical method for finding roots of an equation. Finding the roots of a nonlinear equation which f(x) = 0 is equivalent to finding the values of x for which f(x) is zero or approximately zero. In bisection method to find the roots of an equation we first need two initial guesses xl and xu which bracket a root (Or more than one root), that means f(xl)f(xu) < 0. This ensures that the function must become zero somewhere in between and so it is guaranteed that there is at least one root between xl and xu. The bisection algorithm works the following way:
2 if (f(xl)f(xr) < 0) set if (f(xl)f(xr) > 0) set if (f(xl)f(xr) = 0) set 4. If root is not found go back to 2. In this problem your job is not to find the roots of a function f(x) using bisection method. In this problem you will be given an equation of the form (x − r1)(x − r2)(x − r3)...(x − rn) = 0, so it is obvious that the roots of this equation are r1, r2, r3, ..., rn. For this problem all the roots are strictly positive integers less than 10000 and the range of xl and xu is 0 ≤ xl < xu ≤ 10000. Now your job is to find that for a given root, how many possible pairings of (xl,xu) are there for which that root is found in at most 7 steps? Input First line of the input file contains a positive integer N (1 ≤ N ≤ 30) which denotes how many sets of inputs are there. Each set of input consists of two lines. The description of the two lines are given below: The first line of each set consists of an equation of the form (x−r1)(x−r2)(x−r3)...(x−rn) = 0. Here r1, r2, r3, ..., rn are all integers, 0 < r1,r2,r3,...,rn < 10000 and 0 < n < 11. The second line contains an integer r, whose value is equal to any one of the roots. Output For each set of input produce one line of output. This line contains an integer which denotes of all the pairings of possible values for which root r will be found using bisection method in seven steps or less. Note that as the possible values for xl and xu is in the range from 0 to 10000. So possible pairings xl and xu are (0, 1), (0, 2), (0, 3), ..., (0, 10000), (1, 2), (1, 3), (1, 4), ..., (1, 10000), ..., (9999,10000). So total number of pairings are (10001)(10001-1)/2. Of which only small number of pairings will ensure that root r is found within 7 iterations. Sample Input 2 (x-8469)(x-6335)=0 8469 (x-2384)(x-7423)(x-8718)=0 8718 xu = xr xl = xr xr is the root
2/2 Sample Output 8930 6530