Algebraic Division

Time Limit: 1.5 sec

 

The Problem

Given algebraic divisor and dividend, develop a program that computes the quotient and remainder.

 

Here is one worked-out examples:

 

In the example on the left, 2x − 3 is the divisor and 2x^4 – 9x^3 + 21x^2 – 26x + 12 is the dividend. The resulting quotient and remainder are x^3 - 3x^2 + 6x - 4 and 0, respectively.

 

The Input

The first line contains a positive integer T (0<T<101), denoting the number of test cases. For each test case input contains two string in separate line. First line contains the dividend and second line contains the divisor. The string length not more than 100 characters and contains characters are [0 - 9], x, ^, +, -.

 

The Output

For each test case print "Case X: Q R" without quote. Here X denoted the case number and Q denoted the resulting quotient and R denoted the resulting remainder.

 

Sample Input

2

2x^4–9x^3+21x^2–26x+12

2x-3

2x^3-4x^2+x-3

x-3

 

Sample Output

Case 1: x^3-3x^2+6x-4 0

Case 2: 2x^2+2x+7 18

 

 

 

Inter University Programming Contest - 2016 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS