Find the Right Changes

In early days the concept of money was not there, and people used to sell goods by exchanging other goods. Assume that in a society there are two kinds of goods A and B. Buyer has to pay an amount equivalent to c > 0. If he has the option of giving the equivalent using both type A and B, their unit values are respectively a > 0, b > 0. Whereas if one of a and b is negative it is assumed that seller has the corresponding item for exchange. At most one of the a and b will be negative. Now the problem is to find the number of ways the exchanges can be done for the buyer for c > 0 if it is possible to do so. Input The first line contains an integer n (0 < n < 1001) indicating the number of cases to be considered. Each of the next n lines contains integers a, b and c. You can assume that |a|, |b|, |c| < 231 and none of a, b or c would be zero. Output For each case, if there are a number of combinations in which exchanges for c can be made using goods A and B, number of such combinations will be printed. In case it is impossible to make such changes the line will contain the phrase ‘Impossible’. In case infinite numbers of combinations are there, the line will contain the phrase ‘Infinitely many solutions’. Sample Input 3 3 5 17 7 -23 571 10 36 7 Sample Output 1 Infinitely many solutions Impossible