**Akhil and GF

Akhil and GF

Problem Statement

After dating for a long time, Akhil is finally going to propose to his girlfriend. She is very strong in mathematics, and will accept his proposal, if and only if Akhil solves a problem given by her. The problem is given below. Help Akhil solve it.

Akhil is given two numbers N and M, and he has to tell her the remainder when 111⋯(N times) is divided by M.

Input Format 
The first line contains an integer T i.e. the number of test cases. 
Each of the next T lines contain two space separated integers, N and M.

Output Format 
T lines each containing ouptut for the corresponding test case.

Constraints 
1≤T≤10001 
1≤N≤1016 
2≤M≤109

Sample Input 00

3
3 3
4 7
5 18

Sample Output 00

0
5   
5

Explanation

111 % 3 = 0 
1111 % 7 = 5 
11111%18 = 5

------------------------------------editorial---------------------------

Remainder when `111⋯(N times)` is divided by `M`.

We know the reminder when `1,11,111` are divided by `M`.

If N is even:
`111⋯(N times)` `=` `111⋯(N/2 times)×10N/2+111⋯(N/2 times)`

If N is odd:
`111⋯(N times)` `=` `111⋯((N/2) times)×10N/2+1+111⋯(N/2 times) x 10 + 1`

These expressions are quite trivial. So, We can use a divide and conquer technique to get the solutions. Please follow the setter's code.

 Set by Amit Pandey

Problem Setter's code :

#include<bits/stdc++.h>

using namespace std;

long long int power(long long int a, long long int b, long long int c)
{
    if(b==0) 
        return 1;
    if(b==1)
        return a%c;
    if(b%2 == 0)
    {
        long long int temp = power(a,b/2,c);
        return (temp*temp)%c;
    }
    else
    {
        long long int temp = power(a,b/2,c);
        temp = (temp*temp)%c;
        return (temp*a)%c;
    }
}

long long int func(long long int n, long long int m)
{
    if(n< 6)
    {
        if(n==0)
            return 0;
        if(n==1)    
            return 1;
        if(n==2)
            return 11%m;
        if(n==3)
            return 111%m;
        if(n==4)
            return 1111%m;
        if(n==5)
            return 11111%m;
    }
    if(n%2 == 0)
    {
        long long int temp = func(n/2 , m)%m;
        long long int temp1 = (power(10,n/2,m)*temp + temp)%m;
        return temp1;
    }
    else
    {
        long long int temp = func(n/2 , m)%m;
        long long int temp1 = (power(10,n/2+1,m)*temp + temp*10 + 1)%m;
        return temp1;
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long int n,m;  
        cin>>n>>m;
        assert(n > 0);
        assert(m > 0);
        cout<<func(n,m)<<endl;
    }
    return 0;
}







------------------------------brut - tle---------------------------------

using namespace std;

typedef long long int lli;

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int p=i;p<n;p++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

#define ff first

#define ss second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a);

#define pl(a) printf("%lld\n",a);

#define pi(a) printf("%d\n",a);

#define pd(a) printf("%lf\n",a);

#define pf(a) printf("%f\n",a);

#include<bits/stdc++.h>

lli arr[10000000];

int main()

{

int t;

cin>>t;

while(t--)

{

map<lli,int> ma;

lli n,m;

cin>>n>>m;

         

         

lli nn=1;

int p=1;

lli rep;

while(1)

 {

  lli rem=nn%m;

  if(ma[rem]!=0)

  {

  rep=rem;

  break;

}

else

{

ma[rem]++;

arr[p++]=rem;

nn=rem*10+1;

}

 

  }

p--;

//cout<<" repet with "<<rep<<endl;

 //cout<<p<<endl;

 

 int i=1;

 int f=0;

 while(arr[i]!=rep)

  {

 // cout<<i<<endl;

   

  if(i==m)

   {

    // cout<<" i "<<i<<" = "<<m<<endl;

    cout<<arr[i]<<endl;

    f=1;

    break;

}

  i++;

  }

  

  i--;

  if(f==1) continue;

  

  lli rem=n-i;

  

  lli cycle=p-(i);

//   cout<<" rem "<<rem<<" cycle "<<cycle<<endl;

  if(rem%cycle==0)

   {

    cout<<arr[p]<<endl;

}

else

{

// cout<<" at "<<i+(rem%cycle)<<endl;

cout<<arr[i+(rem%cycle)]<<endl;

}

 

 

}

return 0;

}