github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: A4
problem_name: 'The Rise and Fall of Power'
languages_supported:
    - 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
    - PHP
    - PIKE
    - PRLG
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '4'
source_sizelimit: '50000'
problem_author: admin
problem_tester: null
date_added: 1-12-2008
tags:
    - admin
time:
    view_start_date: 1367924777
    submit_start_date: 1367924777
    visible_start_date: 1367924777
    end_date: 1735669800
    current: 1493558102
layout: problem
---
All submissions for this problem are available.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_ ≤ 109, 1 ≤ k ≤ 9). It is guaranteed that _k_ is not more than the number of digits of _nn_.

### 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 _nn_.

### Example

<pre>
<b>Input</b>
2
4 2
9 3

<b>Output</b>
25 56
387 489
</pre>