Let $n$ be an integer. We define a function $f(n)$ which returns the cube of sum of digits of $n$.

You are given two integers $n$ and $k$. You have to find the value of the integer that is returned when the function is recursively applied $k$ times on $n$.

Formally, you have to find the value of $f^k(n)$.

Input format

• The first line of each test case consists of an integer $T$ denoting the number of test cases.
• Each of the next $T$ lines consists of two space-separated integers $n$ and $k$.

Output format

The output should consist of $T$ lines each containing a single integer corresponding to the required value $f^k(n)$.

Constraints

$1\le T \le 10^6\\ 1\le n, k \le 10^{15}$