You are given a function $f$ which is defined as:

int f(n) {
  while (n >= 10) {
    n = sod(n);
  }
  return n;
}

$sod(n)$ indicates the sum of digits of n. So, f(7689) = 3 (7689 => 30 => 3).

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with two big integers a b (0 ≤ a, b < 10^50,000, a + b > 0).

For each case, print the case number and $f(a^b)$.

Dataset is huge, use faster I/O methods.