SUBSHARD  Subset and upset (HARD)
The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo m.
For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357 .
Input
First line contains T(1 ≤ T ≤ 50) denoting the number of test cases.
Next T lines containing two numbers n(0 < n < 10^{1000}) and m(1 < m < 10^{9}).
Output
Print the subset sum modulo m.
Example
Input:
6
111 9
111 200
456 9
456 1000
1357 1000
1357 5000
Output:
3
147
6
618
333
2333
Time Limit ≈ 2*(My Python 3 Program Top Speed)
hide comments
Rishabh Joshi:
20150531 16:03:34
Can you please check my solution. O(n) getting TLE.


Anmol Garg:
20140630 14:59:03
My 50th. :D 

gabber:
20121225 16:42:50
Use MOD only where you need it! 

R:
20121211 09:57:38
@author


♘Prabhat:
20121012 02:10:15
@Tjandra can you please check my code(ID 7834532) why i'm getting this compilation error


:D:
20121011 21:56:48
Yes :) 

Alex Anderson:
20121009 19:20:17
Just confirming, you guys meant O(log n) and O(log^2 n), right? 

Problem Solver:
20121008 15:11:56
Yeah, solved this problem, it's very nice, thanks. 

Ehor Nechiporenko:
20121004 11:49:46
So nice!!! What about codegolf challenge version of the problem? Last edit: 20121004 11:49:59 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121004 11:10:46
I think 1 seconds time limit is the best setting ;)

Added by:  Tjandra Satria Gunawan 
Date:  20121003 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Hard version of NITT5 problem. 