Given ~2~ consecutive natural numbers ~a, b~ (can be comprehended as ~b = a + 1~) which satisfy the condition:

$$\boxed{a \le \left\lfloor \frac{x^u}{y^v} \right\rfloor < b}$$

Task: (Multiple tests in case) Given ~4~ natural numbers ~x, y, u, v~, respectively. Find ~a + b~.

Input Specification: Data taken from TCPP_ENORMOUSEXPO.INP

• The first input line contains ~1~ integer ~n~, the number of tests ~(1 \le n \le 10^4)~;
• The second input line contains ~4~ natural numbers ~x, u, y, v~, respectively ~(0 < x, y \le 10; 0 \le u, v \le 10^4)~.

Output Specification: Data written in TCPP_ENORMOUSEXPO.OUT

• ~n~ lines. Each line (must be displayed in the right format) contains ~1~ natural numbers ~a + b~, fitting the condition ~a \le \left\lfloor \dfrac{x^u}{y^v} \right\rfloor < b~ (~a~ and ~b~ are consecutive numbers).

Limitations

*This problem will be scored in the Partial-grading system. Therefore, the cases will be divided by the number of tests per case and additional sub-conditions per test.

• Summation:
  • ~20\%~ of the cases correspond to the condition: ~0 < n \le 10~;
  • ~30\%~ of the cases correspond to the condition: ~10 < n \le 100~;
  • ~50\%~ of the cases (the rest) have no additional conditions.
• Per case:
  • ~20\%~ of the tests correspond to the condition: ~x = y \text{ and } u \le v~;
  • ~30\%~ of the tests correspond to the condition: ~u = v \text{ and } x \le y~;
  • ~50\%~ of the tests (the rest) have no additional conditions.

Sample Case(s)

Input #1:

1
2 2021 3 1273

Output #1:

Case #1: 21

Explanation:

• ~a \le \left\lfloor \dfrac{2^{2021}}{3^{1273}} \right\rfloor < b \Rightarrow a = 10; b = 11 \Rightarrow a + b = 10 + 11 = 21~.