P15436 [HackerEarth] Everybody in MIT knows Krishna Sundar is a cool, young and energetic DP programmer, whereas Vaidyanathan Pk is a young and romantic programmer. According to Krishna, energy is needed to
普及
题目描述

Everybody in MIT knows Krishna Sundar is a cool, young and energetic DP programmer, whereas Vaidyanathan Pk is a young and romantic programmer. According to Krishna, energy is needed to code. But Vaidhy thinks that, to be a coder, you need to be romantic.
Whenever the math professor asks any questions, it is Vaidhy who answers it first. Frustrated by his act, Krishna Sundar decided to answer the questions before Vaidhy does. One fine day, the math professor gave the question, which is to be asked in the class, to the class representative, Swagath. Swagath is close friend of Krishna Sundar and he has a grudge with Pk for being so romantic. So he gave the questions to Krishna before the class started, with the hope that he would answer first.

The question is slightly tougher this time. Krishna Sundar has turned towards you for help. The question is as follows:

You are given a string of digits, let s1, s2, s3,..,sn be all the substrings of the original string, which do not contain leading zeros which are all palindromes.

Now, consider the following function
F(n, k) = n, if n == k
F(n, k) = k * (1 + F(n, k+1))

Find (F(s1,1)+F(s2,1)+F(s3,1)+...+F(sn,1))%m, considering s1, s2, s3… sn as integers.
Help him beat the romantic programmer.

Input Format
The first line contains ite, the number of test cases.
For each test case, the first line contains the string s.
The next line contains the mod value, m.

Output Format
Print ite lines, each containing the answer.

Input Constraints
1 ≤ ite ≤ 100
|s| ≤ 1000
1 ≤ m<100

SAMPLE INPUT
1
12
10

SAMPLE OUTPUT
4

输入格式

见题面

输出格式

见题面

样例输入
100 3072007449697535427577656670667399744791454166143162875272767573698264 94 6332123442545362943151236787214819292310292619380 2 476 62 254072198579081329812150489412744714202261 80 031785682263140008460422 10 791418349255137555396480992856042480311019319028103011832280846952676332 8 3876455262539528254123322184279087510037811578031317712367615945694 12 9465400975 98 498353957095802805065306378245130129259666321827027662703729243635901539165 36 0647484706161562182163779396910790338235375420682880581845063222135262318046727679562163362 41 4337751058318423263266240153356481338711869751483282274208083677688528828033437190434032639272 95 55769165775459057305153902313301381506140 90 36090501796735068920911714286820662170448148078984727133 28 04897341200082949674599883743486880464458934939336399376261 27 7414473181752655917233823187888342861252733085566818253138846044362477 20 31827057124473623665147911 8 42099336191241568174671947566496169768998894415526662544016304419678063136390 28 940003920795683223734055685360611966802632389658680641210772101547087 85 0718161933008608229848002655774843950962943756865673 15 2102861906098798922047771337675698957480059323946128388299475926274352204029692098979819 45 745179958759814068896506392967460042328344170189192 75 890295163330173406386902358947063136300393550426786407284066838360958352 53 744212190088138003955654665851322353409709934263755598650494539877315584268280487089133056201509889 64 97545177816174297997829553873054813645535350417937050596419440514318578275625389875637991 36 5481364233666766966968691797316044103 82 851424055010698980468039450031056467200560853074000927676538278885869183209773906205409056 90 9729216970975372225760941805152653948 15 66304782015876506934 79 2203068097673719255468947342731602897912001094468735071156364347783862545707708777202579439831891312 36 852759608 15 5253270496258032819339146516537401162023219735904373035405841 64 8545075019025432997314045118828005015 71 31310244721638628026754120792696427781460881261134 16 42735388314300306059316896692904447483 42 163888839173741191509101807278 86 468183215212379338569462697718350056469093488519546825741929560738836613474636964699818 31 65534980162030923717528 75 67318767568578309964988213549 49 291631930473607227604884538379179685240428837303561313676973 60 2792907025327000948524339108497057471848692007 43 559969167294201225219141586558067273782976506523032372273774 12 8738905759461802603774943851492966031472605546043241253337846966384789482502336004665616040214017324 83 48470377369343344893846688079320789450500462242496003071635659247614049462 37 886235309944528887083945438846549063665 64 5709521848836660617142518513540077644215236325448244139 9 042442071117175119278480852806589339 11 930596446433152959965629216968 8 406414182630826884322523956139904612713 39 1119770768537949956063963889789412813431487503870 14 14528110619087548328378862224409767966914240901438564174315778172414841065 20 2344288384867991474354235187654340189426718192728542535986485705474453611186154513797007887 11 57426825076867 31 8180457531538331215431147634577138362623367959331846192774343402 2 79253926877290434780318915338897623690977301223353777385175673245444423852467 6 53762399887521836174025713096658 80 4871701269183811170487130818670140919 73 74616753510007526844484715528748436367615280708494192552756827586377194 66 046938121517131079249074608213288988667475432679377149232696251950131 12 9284488112473125234927680257281323951879233689463926202295964499888 27 1582055736911729425787141555727447607781206136992231970031372 97 33201258500966779867440898377524106193088366386748330 92 93425522 60 278428705470361209979256636391831983609551263234983306121 16 83168804465457292 42 754408490561419113856027396337268444724704541575 68 046611645927438603718777205415069530241057132968057884 28 928984016105357334056145480770077925755 32 55733606415295567737232571897602539516267934946882749565533072136 32 08361577583118679484564685760233203343407178671092842665895175801 30 5701091020308007341668869557371826458347424637459878625036240640531953262835715 51 4340777675830040153316977 22 994317829 47 2926551784314 37 133184104147715922462178064199540286849588973128891399511609211233208923993088189922005247318186730 18 54328048543692810649948336255517207312947132939092098109810042957816828 31 78116702805714447378336492 11 92269962165337246540757117740958568 58 61121182529 60 4879471722019444818455974240464074845719556341934599138671732319597683122 56 2050813656188922732590114654324 51 3359680271480234894752493935904196164984462554719125840090378673357216394 98 822726341099689406640672745992946661876909 24 763847 69 5854936059490445641420568433721095030547401136956233482904748534516454217994702167192206796574 25 49530517395 41 3780101016753502721591 46 49671927920731404366641253 25 9648368081293144231164442128311307848188045520660948394432336977659780441749077465238386 92 860752869301306031588659780059957270709 41 1221066568553 96 8652414206099196541437404 7 52327499022847673241545457323179192940793737124649225033259541760931959 52 9039351164481847568039313156601163045481898749086695362639959 31 42412098495758151926261054833709942626918875517070492707866099630347186872553578720258785848903 51 610599294687582461813421193539470551346926936262040 68 72017571269453157481262541216671192946232296459483706986733519663819470050 45 759471204233884 87 7023667826870690 70 579244500438391854845311350984645580003281515769054013907304488262005 11 5775385379270896 85 0089970365315932980977938471442619211108022997915657511571047634668303254526182574525380240119699 68
样例输出
33 1 61 11 1 7 3 28 26 37 18 30 27 26 2 2 10 70 12 44 14 14 21 12 68 64 3 45 12 9 53 20 13 14 81 17 20 41 50 1 8 47 26 27 7 9 4 32 8 1 1 21 0 1 7 50 63 7 23 32 72 9 3 28 44 22 8 25 1 27 4 20 29 1 16 8 55 10 52 10 81 11 48 18 17 33 21 81 12 77 4 35 16 10 32 16 37 28 6 58