Back

A. What Started This?

Worth 3 point(s) - Runtime Limit: 3 seconds

Summary

Given a recurrence relation, such as \(x_i = 3x_{i−1} − 5\) and the knowledge that \(x_5 = 1825\), what was \(x_0\)?
If, say \(x_0 = 10\), then \(x_1 = 3 × 10 − 5 = 25\) and \(x_2 = 3 × 25 − 5 = 70\) and so on. The recurrence relations that you must work with will all be of the form

$$ x_i = A × x_{i−1} + B $$

Input

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 10000), which is the number of datasets that follow. Each dataset is made up of one line of text. The first value on each line is the problem number, starting at 1. This is followed by the integers A and B. Then comes k, the subscript of x at which the value, \(x_k\) is given. The corresponding value of \(x_k\) is an integer and is the last entry on the problem line.
The \(x_i\) values will be integers, \(−2^{32} ≤ x_0, x_k ≤ 2\))

2
1 3 -5 5 1825 
2 2 2 6 254

Output

The output has one line for each dataset giving the dataset number, as illustrated below, followed by a single space character, and then the integer value of \(x_0\).

1 10
2 2