Journey to Mars(find first and last k digit of pow(2,n)).

Elon Musk has succesfully built an automated staircase from Earth to Mars. Many people want to go to Mars, but that's not possible due to limited capacity of the staircase and logistics involved. Hence, Elon asks interested candidates to solve a tough challenge. If they solve it, they get a chance to visit Mars, otherwise not. Sam is highly interested in going to Mars. Can you help him solve the challenge? 

The staircase has N steps. One can either go step by step, or at each step, can take a jump of at most N steps.

Elon is interested to know the number of ways in which you can go to Mars. Since the number of steps in stairs can be insanely large, Elon is only interested in the first and the last K digits of number of ways from which he can compute the actual answer with his algorithm. 

Input Format
First line is an integer T that denotes the number of test cases.
Next T lines contain 2 integers each, N and K.

Output Format
T lines. Each line corresponds to one of the test cases and contains the sum of numbers which are formed by first K digit and last K digits of number of ways.

Constraints

1<=T<=1000
1<=N<=10^9
1<=K<=9

If S is the number of ways in which one can climb the staircase, then the number of digits in S is greater or equal to the K.

Sample Input

2
10 2 
12 1

Sample Output

63
10

If there are 10 steps, let's call the number of ways in which one can go is S

let S be of the form wxyz.

So, summing wx + yz gives 63.

===================editorial==============================

To calculate the last k$k$ digits, you can simply calculate the number modulo 10k${10}^k$. For example, using 2n$2^n$ as the number, you must start with 1 and keep multiplying by 2 n$n$ times, calculating the result modulo 10k${10}^k$ whenever an intermediate step exceeds 10k${10}^k$, to speed up calculations.

To calculate the first k$k$ digits, note that you need to calculate the integer part of N10⌊log(N)⌋−k$\frac{N}{{10}^{\lfloor \log (N)\rfloor -k}}$; as an example, to calculate the first 3 digits of 1234567, you need to find the integer part of 1234567107−3=123.4567$\frac{1234567}{{10}^{7-3}}=123.4567$. Now, the logarithm of this number is equal to log(N)−log(10⌊log(N)⌋−k)=log(N)−⌊log(N)⌋+k$\log (N)-\log ({10}^{\lfloor \log (N)\rfloor -k})=\log (N)-\lfloor \log (N)\rfloor +k$. This latter number is easily calculable, and raising 10 to the answer, you get the first k$k$ digits.

====================================code==========================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli power(lli a,lli b,lli mod)

{

// cout<<mod<<endl;

lli ans=1;

while(b)

{

if(b&1)

ans=(ans*a)%mod;

a=(a*a)%mod;

b>>=1;

}

return ans;

}

int main()

{

 int t;

  cin>>t;

  while(t--)

  {

   lli n,k;

   cin>>n>>k;

   lli kk=2;

   n--;

  lli last=power(2,n,pow(10,k));

  long double log2n = n * log10(1.0L*kk);

long double mantissa = log2n - floor(log2n);

long double rais = k-1+ mantissa;

lli first=(lli)(pow(10,rais));

cout<<first+last<<endl;

//cout<<a<<end

  }

}