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}\)