Digital String Transformation Sum

Consider a digit string consisting only of the characters 0-9. Define odd digits as \(1,3,5,7,9\) and even digits as \(0,2,4,6,8\). For any digit string \(x\), let \(a\) be the number of odd digits in \(x\), \(b\) be the number of even digits, and \(c = |x|\) be the total number of digits (so \(a+b=c\)). Define the function \(g(x)\) as the digit string obtained by concatenating \(a, b, c\) in that order without omitting any leading zeros. For example:

• \(g(0)=011\)
• \(g(1064)=134\)
• \(g(822)=033\)
• \(g(1092515503)=7310\)

Now, let \(f_k(x)\) be defined as follows. For a nonnegative integer \(x\), first write it as a digit string \(x'\) by ignoring any leading zeros (note: for \(x=0\), \(x'\) is "0"). Then iterate the function \(g(\cdot)\) exactly \(k\) times starting from \(x'\). Let the resulting digit string after \(k\) iterations be \(x^*\); finally, interpret \(x^*\) as a number (i.e. ignore any leading zeros in \(x^*\)). This number is \(f_k(x)\).

Given two integers \(n\) and \(k\) (with the guarantee that \(n<k\)), compute \[ S = \sum_{i=0}^{10^n - 1} f_k(i). \]

Note: There are multiple test cases.

inputFormat

The first line contains an integer \(T\) which denotes the number of test cases. Each of the next \(T\) lines contains two space-separated integers \(n\) and \(k\) with the guarantee that \(n < k\).

outputFormat

For each test case, output a single line containing the value of \(S\) defined above.

sample

1
1 2

2130