The Rise and Fall of Power

All submissions for this problem are available.
The following problem appeared in the CodeChef March '09 Challenge.
Johnny was asked by his math teacher to compute n^{n} (n to the power of n, where n is an integer), and has to read his answer out loud. This is a bit of a tiring task, since the result is probably an extremely large number, and would certainly keep Johnny occupied for a while if he were to do it honestly. But Johnny knows that the teacher will certainly get bored when listening to his answer, and will sleep through most of it! So, Johnny feels he will get away with reading only the first k digits of the result before the teacher falls asleep, and then the last k digits when the teacher wakes up.
Write a program to help Johnny to compute the digits he will need to read out.
Input
The first line contains t, the number of test cases (about 30000). Then t test cases follow.
Each test case consists of one line containing two numbers n and k (1 ≤ n ≤ 10^{9}, 1 ≤ k ≤ 9). It is guaranteed that k is not more than the number of digits of n^{n}.
Output
For each test case, print out one line containing two numbers, separated by a space, which are the first and the last k digits of n^{n}.
Example
Input 2 4 2 9 3 Output 25 56 387 489
Author:  admin 
Tags  admin 
Date Added:  18032009 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 