계산기

가장 아끼는 오픈소스 운영체제에 들어온 사용자 의견을 모아 보니, 가장 많이 요청된 기능은 기본 계산기의 확장이었다. 제안된 확장 중 하나가 다항식 계산이고, 이번에 만들 부분이 바로 그것이다.

사용자가 계산기에 입력한 다항식과 변수 값이 주어진다. 그 값에서 다항식의 값을 구하라.

첫째 줄에 다항식의 개수 $T$가 주어진다. ($0 < T \le 100$)

각 테스트 케이스는 두 줄이다. 첫째 줄에는 다항식을 계산할 변수 $X$의 값이 정수로 주어진다. ($-1000 \le X \le 1000$)

둘째 줄에는 계수가 모두 정수인 다항식 $P$가 주어진다. $P$는 $CX^E$ 꼴인 항의 합이고, 계수 $C$와 지수 $E$는 다음 조건을 만족한다.

1. $E$는 $0 \le E \le 30$인 정수다. $E$가 0이면 $CX^E$를 $C$로 적는다. $E$가 1이면 $CX^E$를 $CX$로 적지만, $C$가 1이나 -1이면 각각 $X$와 $-X$로 적는다.
2. $C$는 정수다. $C$가 1이나 -1이고 $E$가 0도 1도 아니면 $CX^E$를 $X^E$ 또는 $-X^E$로 적는다.
3. 다항식의 첫 항이 아니면서 $C$가 0 이상인 항 앞에만 +를 붙인다.
4. 이웃한 두 항의 지수는 뒤로 갈수록 반드시 작아진다.
5. $C$는 32비트 부호 있는 정수 범위에 들어간다.
6. 각 항 $CX^E$의 값도 32비트 부호 있는 정수 범위에 들어간다.

다항식 한 줄 안에는 공백이 없다.

각 테스트 케이스마다 다항식의 값을 한 줄씩 출력한다. $i$번째 테스트 케이스의 값이 $V$라면 Case #i: V 형식으로 출력한다. 테스트 케이스 번호는 1부터 센다. 결과는 32비트 부호 있는 정수 범위에 들어간다.