19.py

import math
import collections
from collections import Counter
import re
from tqdm import tqdm

PROD = """
rwgrub, gru, w, wgrrr, wbu, uuww, uruub, rrrrw, rwguu, ugu, ubbu, gbu, rrgbwg, wuuuw, gbb, buw, ubrg, bubrggug, urg, rgbb, rruuwubr, uuu, gwuwubu, ggrg, bg, rgug, rubgb, rwb, gwr, gwgw, gwuw, bugwrwg, wuww, rubbgr, wuwrbgug, bbrb, wuu, brbr, bgrrruur, brgw, urggg, wwbrrr, uwuurwb, wb, ggu, wurub, bwurrw, wru, grrrr, wgw, rru, bbuw, wr, bwbwug, ubr, uwgrw, uuggbu, uru, rrgbuw, bwwwu, bgr, ruu, uwrgw, uwwwwrgg, bgrwu, wuuwrw, rgbu, uwbg, ggwgrw, ruggbgg, uugbu, bgwr, wrurwbbw, gur, bguu, wruww, rugg, rb, gbuu, wrbwu, ubuugb, wgrg, uugu, gugwrw, urwguw, rrur, rbw, wubb, rrrbrw, bgug, wuburb, wrr, wgubwug, ru, wwb, ubgrbub, buu, urgbrrrg, wrbw, wgu, wrgg, gbgr, gbugug, rwgg, wugw, wwrgwgb, bggb, wwbgub, bbwuugr, gg, wrwu, gurbgw, ggwb, wuw, brggrr, rgg, bgrbwu, www, gwbr, rrw, wgruwb, uwwbww, bbur, buwgu, wrrbrb, wub, gugr, ugrrw, ggr, uwwburg, brg, uwbrgbb, buwgb, bwr, ugr, wubbw, bwgbr, uwgrwgwu, ugbu, rbrg, bgwwb, wggurr, bbr, rub, grwur, grr, wwwgwb, bwggu, wbb, brrug, rgubb, wuwb, ugwg, burg, gugu, gbw, ww, ugrwr, uuwuw, wg, wgww, uubuw, ubuw, rur, ubwgrg, rgb, wgrwg, wbg, bgrb, rbwr, gwwgubgb, uurwwur, gbubwur, bbgur, urw, gwug, wuubwwbu, ruwubgw, wuur, bwwbrg, ggb, bgbb, rbguuw, rbu, rwrgrb, gwwu, uwbbwwg, ggguu, bgrr, ug, uww, uwuuwg, rug, uug, bgbuu, brgrbr, gwu, wgb, gggbu, rww, wbrgbr, grb, ubbbrubg, wuwbub, rgbw, gbwb, bbb, bruggw, wrb, uwggu, urb, rubu, gwwgrg, gwggbw, r, gurru, bubrw, bgb, grrr, ugwbu, ruwwrbr, rgu, bbbrbww, wbw, uuw, ggw, gwwg, brw, ubgwubg, wu, wrgb, gbbwb, bww, rbb, bru, bub, bbwrg, rbg, ggbb, wrubu, bgbwrwu, burr, wgrb, gr, bu, guug, ruw, uub, rwgrgb, ruwr, gww, bbu, ubrw, gwbgu, uwugrgr, ubb, ugubrbr, bugw, rgrur, ruuru, bguubw, ggbgbw, bbgu, rrg, gbr, urwwwrbu, ur, bbuuu, ubbbrrwu, rugwrbww, uburugr, rbgubbu, gwg, bwbwgu, gbg, gwrwr, bgw, bwbg, u, wgwrr, br, uwgrwb, wurgg, buwbbwg, wwg, bgrbr, bwg, g, wrwb, gwrw, gb, guu, brwbw, uur, gwb, uubug, wbr, wwr, grg, wrg, bburrrb, uggrrgw, rwwgrwb, wurbr, ubw, ub, gwrrgrbw, uwru, ubu, brr, wggg, ubbrbgur, wbbr, gbbwgwr, urru, guuru, wubrbb, bbg, gu, wubww, ubwbbr, rggrg, bbuu, uguwu, rrwbbrw, gbbburb, gggw, buwru, wbwg, bug, gw, rrr, uwwu, bgbugg, bwu, bgg, bur, uuwgwubr, brwwb, ugg, guw, uwwrg, bbw, bwwrb, rwguuw, gug, brrwu, rgr, bgbwr, ubggw, wwu, uwrrwbb, bgu, wwubbg, wbwrb, rg, brb, wgg, ugrbbr, rw, rbwb, rrgw, rbgb, uwg, buwggwr, wguw, ggg, uwgbgwrb, wurbb, gub, bbwu, rwu, gbrruru, ubg, wubw, ugw, uggbuw, uurbb, rwbr, wgr, ubwbrrw, ggbgwr, uu, bgww, gbbwguu, wwbr, rrugbwbw, uw, bggwr, uwu, wbubr, brrr, wrw, wggw, ugur, uwr, bwbgw, rbr, wwgw, uwub, uwug, bbwbu, rwg, rgwwrw, grgwwwu, bb, rrbubgrw, gugg, rrwuww, urwu, ggwgr, wugb, ubgbb, gbwguu, rrb, uwguugw, rwr, gugwgu, uwubu, bwgw, ugruubg, wrrg, gwubwu, wbuww, bgwrw, ubwrgw, wrgrwgr, wbrgb, wrbgb, wggbbbg, uwb, wwuw, brbguuw, ubruw, wug, gbuwgw, wgwub, wrbg, uggug, rggb, wuuwwr, uuuggb, bwgu, rbgu, ggrbrw, wgrrgu, grw

bwbuuguwrgbrgruggbbgrrwwrgwggbwurwgrbubbrrugwgruuug
bwbbwrggruwwguurbugbubbgbuwgwggubwrwwgwbrrbuuww
bwbrrurrwbuuubgbguwuwgruuwbggggububugwgwruuu
bwbugbbwbgwbubguubgrgrwbuggbrggwwwgrwbgububr
ggrggugwgrrrggrruggurggwguuuuubwrurbgrgbwwwuurg
bwgwuwgrwgwurwbwwrwubugbgwubuwbggbbwbrbwbuuruugwbwrwwuwwg
uggbruwbrwbrgbbgbuuwggwrbgurrrwbwgbwbgbubrwrugwugbwrwu
wbrwwrurggrwuugbuurubbwwugwuuurwrggwgrruuubggwbwrbr
rugurgrrugbwbugwguwgbrrwwgwbgrgwbbgrrguuurruubuuggurrbwu
bwbrbuubuwuuuwwbgbbruugbbgrbgbrwubbuwguruwbwggbbuggruubbu
guggbgwrbrggbuguwbwgwbwuubbrgwrggrubwwggrwr
buwwrgguwbrurwrgburgburbugrbruwwgugrbburwuwwg
bwbrrrburwrrgbwgbgurwuwrgwruuwrrwbrbwuuw
rwrwgbbwbrwwuurwuwgurwubgbbwrgbubbgwrrgurubbrrrbgu
brgwrbwubuwwwuuwwruwwrrbbbgwrguburbuurubgu
wwrubrrrrgugwrbwwbgubrwgugrugrbburgbrwguuuwrurwgubwbgbrwg
ggurrwrrwwwuwrwrbbbwrwbuburbrgubbwrbbgbbgbrgwrwbu
bbrwwuwubugwgggwgrgbguruuggggwguuwrgwubwwwuggbrwguubu
guwruurbuwrrgggbgrrrrwurwwurruugggrwgwwbruugggrrbwgub
ugurwbbbgrrbbubrurubuwgguurgbbwbrubwbwgwugwbwururrrgg
wbgrbbbrurgrbgrgrwugbbwburbwwrbuwuugbwgbug
rurbbbgurrubwuuwgwubggrurwugguugbwwbbrgwwr
urubbbgrrwwwgbgwruwbubrwuugruwwrruwrbbrgrbwrubrugbubbwggwg
rbguwbubrbgbwrbrburrbgugrbbbugbgrwubuwbubgrruugrwggburgg
wbbrrgrugbugwubbwubuggrurbubwubbgwwuguwbrbgguguwurwuwg
bwbwwrwgubgugrggubrrubbgwbggbwggrrrguwrwuggrrgwubg
brrbgrwrrgugbrugubbuuwgurbgruurwgugrubwuurugwrbbrbggwrb
wbwggbrrgbgwgrwgwburrwrgrrrgggbguruurbbuwrbgrruubrgbgru
urruurugbgurwuwugguuwwrubrbgugrugrwrrrubggwuwwb
bwbbuuurgrrgguwwgwwwwguwugrbwbuwgbgwggwbrgurbbwrb
bwbubuwwwuwugggbwrwrbgrugwwbgrbwbuugwrgurbbgubuugbr
bwburrwubwgbbwruuururwurrgruruurubbgurrurbgruwbgubrwr
wruuwuwbrrggurwugwwgburuuwrbwrgbgwbugrwuuburrwruwuurug
bwbuwbwguwbbgrrgbbuwgbgwrbgrrwbrurrubbbgbbwubgw
gbwrbuwrugguwwwrrbwbbgubgruugrurwgwruuwrwgwwubbggwur
ggbrugrwrbggubugwgurbuuwubbwguugurgrgwbwrwgwuwb
uurrwbrruwwgggugwwgrrugbgurbgrgwwbgrwwuwbgwg
bwbbwgugrbbgrgwwbgwwgbwburugbbrrrwwgugwggwurgbwwuwrwwwwgbgbu
bwburwruwgwwburgwruugrbbrbwwgwuwurggguwgrwrggbrwrruugbw
bwbuuwbgbuwbgurgrwugurgwguwwwwubugwggwuguggub
guurgguburubgubuwrruwbubugrugbgbwuuwwgwwggrggurwwrw
bwbrbbwbwurgbwrbbrrwrgbbuwbgbrgubbbrbrguuuwbgrguuruugwu
buwwggububwruwwurgguwwubrwgbwggugguruuwgwubrbuubgrww
bwburwwwrubrgwgwrbwbwwuwwrugwrbgbwugwbgg
ubrwgwrgggbwwgurgwgwbbwrwbbwrgbrbwgrgbuwwbuubwu
wgbrwgrrgbggbwbgrrwwbruwbwuugwrbbrgbwbgruwbrrgbguu
bwwbwbbwubwuggubuwrwwgggwrbuwbwbrgrbbugrrrwrbruugb
bwguruubgggbgbuwbgwguubgrrruurgbbgruubwuwu
bwbruburgwuwrgbuugrruwwggggrbbwuggwwurbuguubbwuugu
wurbgbgbrgwbrbuugwgrrubbbrrwuwrrggwrguuguuuurgrwrguuggg
wrburgbwwuwwrbrbgurguwwruwwuubgbgguwububbrgwrwbrgbw
bwbrbrruwurgurrrrwwwbbwrbrgrggwguugggbuggwuguwubrwuubrbb
gwrbgrwuurubgrbrbuwgwwguwwwbwwugbbbuuwwuuuwbbwwwg
wwbgrrrbwwuubrrubwwugwuruggbwuuruuwgggugbwugwgwwbgwwr
ubbrwrrrgrrgrgurbwububgrgrurgubrgrrwgwrrbgubgurgbugbwbr
rwwuwgbruwuugwuwguwrbbrubugwwwgwgururuggbwbubu
bwbrwrwburwgrwrgrbwwububbrgbbbwrgwbbbwwugu
gwwbruwbgurrgwbrrbrrwwwubuuwuguurguurrwwwgurgrwwub
bwbubbrbgurrbgbgwubrrwuuwbubbgurrbrrwrrrugurbgrur
grrruuuwgugbwrrbrbgbuwrrwggwrrgbubgrwwbbrbggbwgwrwuwuwwgu
bwbrbrgwbbubrrwururwguwrwuwguggwururgbgbwrggr
rbwgbrrruuuuurbwgwubggggrwrrrrurrgbbbbuggrguwrbubuwbwbug
bwbwrgrrgwrrgrbwbwrbwbuwuwrrbwrwgbbrbwgr
rbbrgwubuuurgrrgrwgguggwrrbbruugrgubugguuwgrubwrwb
bwbbwwuwwgrbrwugrrgburwuwbwbwgwbbwrururubgbwwgwwrgrg
uuuwbrwbwggbwbrgwuubgwbbuuggrgurbgwruguggguw
bbgbwruuwurgbuwbbbruugugbbbruuwrbrrubugwwuwgwbg
wbrugwggwbbwrggwbgrggubwgruurgrbruruwwbwbggrwbrrwbggwrubg
bwbbuurwwwgbguwguwrgguwurburgwgugggrrbubg
grrbggbgububbbrrbuugrbwbwrgbrbwgwwrgbgrbwbrurbwuwgbuw
rbgurbwrrbbggbuubwrugbgrbwwgwbbrbwgrubrgwuugbbwwggwgu
bwbbgbrwgwbugrwbbbbbuuwugwuuwwrrbgrwwrrwguwgrbbbr
rugurwbwrurbwurwgwbrgwwrwgugurubgbrgrgbguuwguuru
bwrggrwgwwgubgbuwbwrrgwrguwbbwuburgrbrrwbrruuwu
bugrrgrbwbgwwruubburrrguwwguruuwgbbbgbwrgwrubrggrgbub
bwbbrwugwuwgbgbruwbwgbrrgbruuruwuwubgwgwbwg
gwbbbggbgggbubgwugwrwwurrwbrgwgwbbbruwbuugwrubbb
uwuugwbwrubbuwwbbwgwugwbwgggbrbrwubgwwgubbgurbrwubwgbr
wgrbwggwrgwrgrurrguuuwwbbrrrburuugbrggggwrrurruwwugugwgbbg
ugrbggbugwbbbrwubggruruwbrrugwgbwwuugrruwrbw
rrwuwugbbwbuwwwrwwwuuwbrubgbrggubrwwrwbwbuuguwwgubb
wggrgbbrurwbwbuubuwuugwgrrgbbubgrburgggugbwrr
uurbbrububuugbwwruwbwuuwbbbrrbubgrwbbrwuuwgguugbguwr
bwbugrgbbwuubuugbrbbubgbwuubugrrwgrbrgugguwuurbbbru
bwbuuurburbgbbgrrruurrwruwurrrrgbwbbgwguuwwrgwbwuggr
gwrrbrurguugggbugurruugwrgwrwrrgrggguuuwgbgrgrwwugwwgug
wwrbrwrrwbbwbbruggbwwrbwwururrrrgruuggubrg
ruwwrrbbbwurwbuguurrgrrbrbubrbgbbuugrrgggugurbbgrrbwuggug
bwbrwwuwurrgwgbbwrrwrbubrgwgrubwubwbruwbrbbwwwuuwgugwwr
ubbgbrbrrwgwuwwurgrggrbrwwgwrurggbgrgwurburrgrrb
uwwwguggubuwrwrrrugrwguuruwbgrrrbwwgwbururuwwrbubg
bwbwwwgurrwrrgrwwbgrrubbruwugubuuwrwgwburbwggbrr
guruwwwbruubwbrbrubggwgbubuuugbwgugbwuwuur
bwbwwurubbbgurrgwbgwgrrugwurwggwbgubbwrugubggruurgbbr
ggwgwrrgbrubuurrburgrrbrgwbugruwbrwgrbugbgur
gwburguugbubuwrwruwrrbuwwuuwrbwgwgrwbgbrbbbgrrwwggw
rgwbuuwugrugubbwgrugbwbugbggggbbgwbwrgrwbgruwbbwu
bwbwwwggbgwugugubgrrwbugwrubrbuurwubuggbgruw
urbbgrruwwwbbubgwggrbggrgrwuubuwbwguwugwur
buruggwwwwwbbrrurgrurwrgrrrrgubwwwbrggwurwurugbwrwbwgg
urguwruwrubbruwwuwggrburgrbwburuubrgrggwrggrgbwbburwu
bwbwbrrgrgwbbrgrbwbrgugrurbrwrwrwggggbuwugbbwwuwwrrur
urugwurguuwurgrwgwrruugrrrubuwwubbubwwbrbrrwwguwbggur
bwbrrwgbbrbwwbbubbwwgwbuwurrrrugbwrguguuurbrwuwwrgb
gwwbgggrrwuwwugbwwurrugwgbgbuurbgwbbgubuwgrwbbu
bwrbwbrgugrgbbwrurwbbwbbwrrwugrgwbggwugrubbbguu
wgruuuurwbgwugburuugubggwburbugrbggubbuuggbgg
bwbwbggrgwrbwwuwrrubwurugrubwgrbrbugwuggwgggrubgwgww
bgruwbggrrbwgrrururuwbbwwrbgubrbrwbwwbuuwugwwbg
bbbuwurwrbgruruwgbugguggbbbwwwwrrbuwugrgguurubggwgbuwugbr
bwbburguruwbggwugurwwuurwwbbgrbwgbgwrwbubbrw
bwbwgrbgbuwugguwwrgwbrurwrrurwguuugwwgbuuwrurgwruubrwbubwu
grbrbrgrgrbbgbgrgwbwuurbgrbwbbgwgrbbbugbrr
bwbbbwrbwggrwbbwgrbbgwurubbggwbggwbbguwrwwuuwgbwbgrgububgg
grrgwgrbugrugubwrwrgugbrbrrrbgrrbrurrrwrurruggrbggr
wbrbwurrbubwwbgugggwugubgguuggwwwwgbugrwrwgbbgbrggwwgru
bwbbwbbuwrbwrrbwwguwrrrbbrbggwgwgrrguwrgrrrrwbwru
bwbubbgbgubgbwwuubuuggbggbbuuwbrgrbubggwrwrgugbwwbbbgbuw
grrrbrwwwgrugbbggbuwggbbuuggbbgrburbuwwrugwwubwubggbruwugu
wrbwrggbggrwgrbbgwgbwrrgwgggbwwruuuuuurrbru
burugruubgbrbubbwubwbugwuuwggbrgwrbwuuurwrwuurbbrbggbb
bwbwuubwuwrwrbrguurubwrwbbubrbbrbugrgwbuggbuwwrrgbuggwbrrb
gggwbbguwwrubrrrrbrwrgurruubwwbggburrwbbwbrrrgugw
bwbrububuwguubuwubwurruuwgrrubwrrbuwugwbwgrrbgrwgwruuu
wrwwubgguurburgwggwrwbwrwbwuwuugbugwuugbgurrrgbw
grbruuurububruubrrrbbggbuwuwrbburwgbwrbrrr
bwbubbwgbruwburwubwruurrgbwuwgrrrrwuwuwbug
brurggubbruburrrrrugrgwwuwbrurggwuggurgbbrw
bbbbuwbrrrurubbwuwrbgwuwwgrrbbrubrbwgbguwbwugrbbb
bwbbwrubbggrgwwrwugbggwrggbuggrwwwbgwwggbuwwgurrgwgbuu
rguggbwrwbwguwbgbwwrburgugugbugwbwurgrbwbgrgrbgurggbgwb
rbbwruwurwbwggbgbuuwrbbugwurbgwubrwuwgrgrwggubur
bwbwbbbugrwwgwgrwbuguwuugugrrrurgububuwgwrg
wbuuurgbgwgugburrrrggwrururwrrwgurwugrbwurrwbguwgbwbwuuw
wgggwbubbbuurugugrugwgugurrwwuruugguwgrbrubgburgwrururbg
bwbbgrugbbrrwgbbrurrggwurwggbugggggbgubgwwrbrgbgrwgwwgrg
bwbwbubwrwgbwguwbwwrbgubgbbrwwrrguguwbwbg
bbgwrbwbgrwbugrrgrgurwuwwwbugrbbrgwwburwbubwrbguur
ubbwrgurwrguwwgrrbgbugrwbbrggbbubrwgwwguwuwwrwgbubwugb
bwbbbwgrbgbbbgruwwurgugwuwubgbgwrwuwrrgggwrrrugbwbwwubr
bwbugurggbgwbwwbrbgguuwgbbwbuurbrbwuwubwrrwgruru
ruuuggbruggrgrgwrwuuggrrruwrrbwruugrbgbwubbbwrbu
bwbrbrubrgbrwbugrrrrggwrgbrwuuwbrbgrbrbrbruwgbrgbwbb
grbrwrgrwuwwwububbbrubggwwwwwgrbwgwuwrwggbgbwwgurwugbguwg
uurgrbwwwuugwruurugwuwuuwbgrwbgrwrguwbguwbgrgurubbgwurgbu
bwbuwubwggruwbwbbggurwrrburgrggwrgbwubwwubrbwgwbwuwubwruggb
brbwwbrgwurrrwbbuuurwuwuwgbrguwbbrrrgrbgubwugbuwuwgguugrg
bwbuugburbbbubbggwwbwurrgbgwrggbbgburgwbuwuu
bwbrbrwurgwrgrgwwuuugrggwrgrrrbgrubgrgwubgrbwwbwbwrrugburg
urgggbwbwggrbrbbwurgbwbgrwrgugrurbruubwruuug
wrrwbgrgggbubgwguwugggrgrubuwrgbgrrrwurggurwgrwgruugrr
uubbwbuwgrggurggwgrrbubugurggrbrgrburbgbbbuggbrwuwggub
wwwgrrwbbwbbwgbgwuwgrrugbwbwrwwgrbugubugwwruuugwwbug
gbrrurruurbbgubgwuurugwbrrgurubbuggurgrbuwgr
bwbrbuwurrbbbbrwbrgwrwwwgrbburwwbgwbwrgbgb
bgrwubgrrwrubbugwugwugggrburbbuwbwrggwbgwurwbubuuu
gbrgbwbrwuguwbbrrgwwwgbgrwbuurgrgwggrbwuwruuuwrrurgw
bwbubbuwguuuugbuwubbrwwruwgubbubrwurwbwuwrgrw
bwbbburwbrrbubgrwgwbbrrubwubruubwwwubgwwguwgrgwuuwrwgbbb
guwwbrbbgruwurbwwuruwbbuwurgwbgrgubrgrbrubbg
bwbbruurbrwguuwrrbggguurwrwbuwugbrruwgrwgwubbruur
bwbbrrugbwrbbugrwgrbwugwuuuugugrurrrgwrwubbwwu
rwrrgggrggbgwggwgbgrbwugwrbgbrbwrrrrgbwbggg
gbgurwbwruuwguburrugrrwggwrbrugubbuwggrbbugubrg
bwbwwgbgbrbwwwuwrrrubwwwurubuugguuwubrgrruuwuwubbruu
bwbwggrrbwrgrwbgbgbrrwurbgwuwwwwgwrbwgwgbrugggbwrrggrg
rwrbbbuggrrubbrwubugwrbrrguuurwgbuwurwwwgwguwwuwwbbr
rubbugwgrgwrgrrwbgurrbubbrbwwrbgubgurrbbbgrgwbgwrrurrbg
bwbbbbwgwrbggbgwwgggubbrgubuuugbbwgwbwrgbrwguwwwugrrgrr
gguurburrubbrrbgbbgrbrubgwrgwrwgwbbgrburwwwrbugb
uuwbuggwgubrbwbruurbwbbwurbgbwuuubrwbwgrgruuugurwwu
bwbwbbwrwwbrrbuwrwwurrrrruggbrgwbbgubbrbbrgburwgugbwwgwrwgwg
uggrwwurbuwbbbrgrbbbbrwgugwrbwrrwbrgwrgbrggwwwbgbwg
bwbrbuugbwgwrbrrgwbrguwuurrbbrbwwrubwuubgubgbguubrrw
bwbugrrwgwwwubguwbwbugwwurwgrrwbgbrrgbubruwrrbggrwbuwubrubww
wgrbbwuwwbgwrwbuuwurwurrbbgbruwbwwurgbbrbrwr
bwbwubwrrrggrwbggguurbubwrrbwwugbugrggugwwwgwwwrrb
bwbwrrrrrbwgrugubwwbwrbbbugwbbubrggugbuwwuwbbwwrbgwugwwg
ggubuggwbrwwwbuuggwwuubwbgruugrbwgwruwrruwrbwgrrwwu
bwbuururrrguwwuwwrggwbwggwgwwgubgbrwuuwwggrubrgrugru
gbubugwbgwguurrrrwbbgguuwwggbwwrrwrwwbwggbwburwwbbug
bwbruggguwgwrwgwrgrrburbbggguubrbbbgbrwwrbuwrwwrbgwbwwrwwug
bwbbrbwggugugggrubgugwrurbbwgubggrbbrbwb
urgugwgbwgwwgrwrbubrwurgwwgwwuwbbrbgggrbww
uwggrbburguwubgbbruubwrrurrguguwwguguwbwbrgwbu
bwbrwwwgrgguwuubrggwugwuggbgbbburrgbggrgugggrwubwugb
bwbubgrwwrubuurgbbugggbrrubgrgrbrruguuwgrwrwbbwgwwwurbg
bbuurgbrgwgbbgbgrrubrruubbgggbggwgugwgrbrwrrur
grrurubwbbubgwrwbrbwbrguubwubbrugrwburuwbubgrwrg
wuwgbgwrubrruurubwrrwrwuwgwbbwgrrgubbgubbg
bwbbbgrgrrurrrrwwugwuwrburwgbbggbrgugwwruruggubbru
bugwggggbwrbwrruubgruwrrbrbbgbwuwbggbwwuur
gbrrgrbwbwruuuuwrwgrrugurgbubbgwrgwurgbwgwbwguwbwrwwubgb
bwbbrgrrbwbwgbwwgrwwwbgrwwubbwuubbrrgruuuwuubb
bwbwrbwbuugbugruruuugugugwrgrwbugbrrgwubbwwggrruwug
rrwubwurbuuggwgbruuwgwuggguwubububuwuggbwru
bwbbbggrwuwbuguurgwrwwwgbgrbrrgbrurwbuwburrugwuuguw
bwbruwbbrwuguurrbgrgrwguugbbrwrrwbbgwbuwggrw
bwburwwugrwgbwuurrwrgburggwwbbggugugrbggrbbrrggugbubrb
bwbubruruurrrbrugrrurubrruuwurugbwwwrbwwru
bwbrugbwgbguugwgubugugbrbgrgrbgbbgwgwggbu
ubrbbbgbbuwggggwbgrgwwwbgurubruguugrbwwgbrgrgwuubrgb
bwbbbgrwugwurruubgurbwgubwubrbbwwbgubuwbg
rrgrbbrwwwbgrgwgugrwwbgbwwubbugwubbbbggbbggrwrrwrg
rbwubwwrburuggwbwruurgwbrrruwuwrbgwwgrruuuwb
bwbrugububuuubbbrrwubgrgugrwwbgguruurgurwruubgur
rggbbbwwwuwgbuwrrrruwbwgrwwbggugwubrwbuwbuuu
wbrgrguuuuwwbggwwwgbrguugbrwgwruuguggwuwbuwbbgruwburugurg
bwggrwuwgbbrggrugwwrbwbrrruubbwguggwbrbggurubrggb
uwbugggrbwrwrwurrwwwgwwugwuggwrubgrwgwgugggwggbg
wwrgwuugwrrbrrwwbugruwgrugrbgwuuwbrwbwuwbrgwwrwrwgrbgubb
bwbbggbguwruuwggrbgrrrgwbrwwbwgrwuubwwburgbbbbgbrgrubgwuwg
bwbrwwubbugbrwbgwrubrgubruggwwggbgrgurgrbrrbrbwwbrggg
bwbburrrwgbbgbwurrbgwurggwubbgrwuwbgrbgugrubwuurruurbrbr
ubrrwrguruwbgubuuuuwgugbwbggwgbrgruwgguwubrbgrbbrrggwurwgr
wrbgbwggugrurguuwrwwubwuwwuburbwruubruugggbg
bwbrrubbggwbrwwrggrbrgbrwgrbbrbbwburwbbruruug
bwbubuguwrbwgwuurrrubrgrbuwbwuubwrwuwrurwwbb
bwburbruggbubbrbwugurbwuuuwgwubrubggwugggwwbuuwggwubr
bwrrgubuuwwgrwubbbbrrwugbugrrrbuwgugbuuwwgwrb
wburgbugwrrbwrwrurrgwbuwgurgrrwubgbguurbuguwr
bgugbrgbwuwugrrrrrbrbgwggbgwgbrbrugwrbwwurgubrgrrburugw
bwbrrgugbbwggwrbbruwwubwgwwurbbrwruurgggrguwurwrgbrurwugb
ggrwruwbggruwbbuwrgbuwwwbruuwrwwrubrwwruurrwwurr
rrwrrrbrwuubgbuwgwwwgbgguggwububugrwggggwrgrbr
bwbburwuwwububgurwwbgurrbbuugruuwrgguggrbwburgurgbbwwrbbgw
wrurgbrwubgrbuurrwruubggrbruburwurrubrbwbwbgub
bwbbubbwrbwubbuubrwgbubwgguggbwuwwwwurguurgbgrggguwuwrrggrru
gwbwgbrwgrwgbwrrbgwuwbbbwrgwwubwrgguubbburwbwbbrwwrgwrg
grbbguguwgrbrrwuwurwubggubwggwuwbbwbugbbrbugubwrrgwuugubrw
ubuuguggwwurwbrwgrwugrbgbwbbrwuwgguggggrbugrrugrbruubguuww
bububuwwrbrurbggguuruubwbgrwggwgbuwubwwburg
ubuuwuurugwbuuuguwguurwbgrburwbrrugbuuuwrgwwwgugwwwwrrgwg
bwrbwbubururbubggwggwruwuwwgggbgggwwwbggububuwugubwbgrgbww
bwbrgrgbbbwbubwrbuubwrggbgbugurbgrwwbrwgruu
uugggrbwrrbwgbuwurgurbugwuuwgrggurrgwuwrbuwwgw
gggrguruwbwwbbrwbbuwwggbuwurgwbgwurwbwwubwub
urbbrruugwrubburgrwgbuggburguurbrbgbwwburwwrburrwubwwbrrwb
bwbbgwwggwubwrgbrgwwgbgrwwwuugrwgurrrwur
bwbwrgrrwbugrgwgggguuwrrbuggwgbwuwguubwwurugrww
bwbwwubgrrbgrbggwwbwgrwbbrwwuwwbgbwwubwwbwrwrbguwgurrrbugg
brgwbbuguuuguwgrrubgwrbuwbrubgwurugwrbwbgwrbbgrbuugurw
gugrugwgwuubuugrwwwgubrbwrrgrrwwgwggrbbwrwgbuuugwrgwr
wwubgbgrrbbgguwugrbbugbbrrwuwrrruwwubwgbbwgugggrwwgwwuuww
bwbbuubggwruurguuubrrwubggbubgwgubwwgugwbwuwrggubwr
gwrurwrggbwrbwrrwwbrwrbgurrbuwwwubbubrgbrr
bwbbrgurbubgugrburrgbbgbrgbbbrbuubbrrrubggbgbubuuubrgwr
rrugwguuuwbgugrrrurbgrbugbwwgrgugurugrwruuuwgugbrugw
rrubwrwrgrbwubugugwbgrwwuwgrruuwubrwuugwrbrw
ugrbbgburwurugbgrwbrwguwbubgrwwwbwbbuwugwbgrw
bbwbubwrruwuwwggbbbrgbgbrwbgrwrbrwurugggwbrgwgwgwrbg
uuubrggwrrwrrruwugrbrrwgrgrwwgbbuuugrubruuu
bwbrwbuubwurbuwgwgrbrgubrgurbbbrrwwbbrwrrgruu
rwwgbrwurguwwwwrggbwuruwuuurubgwruuwbubwwrwrbrwurw
bwubwbrbuuwbubgrwbbwburwrgbuurbrgbrguurwwwrbugbggbrwrr
bwbruwuwrwbwgrggbwwwbruurubwwgwubbbwwgbwwwgwrrwurrwurubbgu
bwbrwrrwrgwuwuurwbgbgugugrubwgurwruwbubwuwrwuur
wgrbgwubruubwrgurggubrgurwggbuuwrububgbgurub
rwbgbbbwrbgurgwwbrrwrwuuubbrggbgwwruubgbbgbubrggugububrwug
rwugggwrrgwrrgrgubuwbuwgruguubggruuurgrurgbrrrggbwrugbgrb
bwbwgbugbbrwbbbwwgwbburbwwubbbwrgrbgwwwrburrurrwwrrrruguuubg
wwgguruwubwgurwrwubwbrwuwrwrggrwrgwbuurrgbw
bwbuwbbwwwburgrrrrguwuguurwggbgbrbwurguwrurur
bwbubggbbbrbrbbrbrwwrwwbuwrrrggrubrgwwuwbuuwgurug
bbbrrubgurwururwrbuwuwrubuwuugburbgrrubgubwu
bwwubwguuwrrruugwwuggguwwbrrurubgwgwubggwrwrw
bwbbwbwgwgbrgrbrgwrrrubrgbwwgwrrugurggwwuwwwwrggbg
wburguugugubwugwwbgruwgrwurbrwugubggbbrwburub
wwbbgwbubrggbbgwurrwwubrgwuggrugbrruuurgguuwgwrbrurrur
bwbburbgbgwrguubwgwrbrruruwbwbrbugwurbwwbrrur
wbbgbwgrrgrbrrubuubuwwbbggbwwgurrrbruwbbwbw
bwbuwbgwrwguwwubruggggwbuuuwguwgggrubguubbbrrbuwugwbbrgbrgb
bugururrgwggwwrbbubwbgwwbrwgwbugrrrrbwubwwbwrugr
rwbbbwbbrbuwgggwgwgwubgbwrrrwwrwgrbrbbgwwg
bwbbgruuubbbrrubguwwguguwrbgwwrwuwgwuwbgbrur
gburrwwburbbwwrrwrrrrurgbuugwrwwurwbbbbrwgrggrwu
bwbbbbrggubrbrbggrubrbwuwwrwugbwrrguwggurbgbrg
bwbrugbrbbguwwrrurbubbgburgrrrggurgurgwgwwbbuugugrggw
brwbrgwuggwbwurguwwbrbwubugwbgrbubrrurbwbwuurruww
bwbuwwburwurbwwwuuubrrgbbbwrwgrrrgbrurguugwwg
bgbbwurrwuwbrrwurubrgrwuwrwrgwrgbgwubwwbgbguugugwrbwbgguuw
ruugbbrwwguguwguwwbwbwubbbrgbubbrgugruwgbgwrbggruwww
rbwbburrwguuugbbbgrrruurbbrbggggbgwbugwbuwb
bwbrrgrrgurrgbugbwrbwwubbbwruuuugwrbuwgbrrwrwrgr
rwuwwwrwrwburbgubwuwwurubwugwgbwubbruruubuuurubgwu
bggrgbrurgggrbwbwrbwgbrwgrwrubbwrwggubgguw
bwbbrgwbrgrrgwrrugwugwurgugwrrwubwbuubgug
bwbbgrbuwgggugbwwwwgrruguubwrrgwuuubbuggbrguuuubrbrugugwuw
bwuubrrurbwbrurbruurbgbugrwwrbwuuwgrubrbrwbrrguwbbruugggu
rwrbubrwuuwggubgwuwrbuurgruggrgbwwwbbubgwubwgwgugbwwrr
urwuwrubrbbrwbrgugbuwuuwgbrbugwbwbuwgbruruggggugwuwgbb
uuurwrurubgwwbbrrbuurwbbrggggwgrugwrbrwrbggugbubuggrbwuub
rrgubwrguwuuuuwuwrbgugbgbbguubuurwrgurbrrrrbgwruwurwrrr
bgrgwrbrbbbbggrbgbrgggrbgurgbbuwuuugrurgbwbwgrbbwrrbwrr
bwbrrwwrwwgbbrbwwuguuwrgwrruuwgbrrbwguggbgwwgwrrwr
grggubgubbwrrubgwbugbuwugwrrgrbwrbrgubbgbugguu
gwwubwwuggwbgubbgurgrbugwuwwurwguwuuurwwguurwrwgrwr
bwbwgwbgrgrrrrwbbbgwbrrbuwgbrugbbggrbwurugwrbwwrggrwb
wbgbwrbubbuuruuwguuwuurwgwuwrbwbbbbrbgbbgruurgu
wrruurubwrwbuuubbrbgurwrrgrubuwggggggbbrggbwuuugrbu
bwbrbbbggwubgbwuuwwrwbugurwgugwbwbbbuwurrruubgrwuwbr
brrruuggwguwgwgbwgguruggwrugburgubgugguwuuwgrbrbwubuuuubgr
bwbrwugrwrurwgbgwwuuwwurrubbbwwgggrruugbuggbguuugbb
rgwgwgwwrrbubgrbuugrrugubrgrbgrrwrgbrrrbbbugbgbbuurguuuw
wgbbubbgguubuwrbwrgwrwuwuuwgbwbrbbubrgbwbrwwgbubrrbbur
rgrwbggugbrugwrrggburwbbwrburugwbrrgbguurwrggg
bruuuuguuugwgugrrgrrrubrugruuwgbwbwubwgrwurrr
urwrwrggwbbbrbrwubgbbgbbrwuwwbbbrwwuwuguggwwuurubgru
bwbrggrwuubrwwuugwugbbrrgbubbggrbrgwgwbwgbwwwrgbubu
rwuuruwrguggrbgwggbgbwgwrurrrgrburrgwbguuruwgr
bwbugbrubuwggwgrgubwwuuurrbubbuwwggbgggwwgruwgg
uwbwrguuwbbwuuwuruubwbwurwubugrgwwgbwuubwwbuubbgbgwrg
brgurwwgggrbgwwugubwrwbugwuuwuwwuurugbwubggwwwwruugurrg
wgwwuwugruuurguwwbugbrgbgggwwbbggwburbgbbwwgbwwwgruurgg
gbwbguurgubrbgrrbuwgbwgggbguguugwbbbgubwgrwgggrrwbbr
wurubbruwbbugrgrruurrurgwburuuwubgrbrggwgurwbwggbgwu
gugbbwgggwurgbrwbgwwwbuguuwwggwugugugugguruwuwwb
gwrbgbbwgwbwrwgwwwbwwurubugwbgbwrrwruwggrbgbgbwgr
bbbbgbrwrwubbgrgbbuggrrrrubrruuburbbgwbggrbwbug
bwbuwugruugwgugrurrwuwurbwubuwgwubrbbuubbbbw
uwbbrggwuugrbrwrwwwbrgwruubuururrwggwgrggwwguguugwuru
bwbrrwubwugrubbwgwwrruwgwguggrwbrwwgwggrgwwrbwu
bwbugrgrgwrwugbwurgggwbbwrurruubuuurbbbuwgwurbrbwwububrg
bbrrwwrbguwwurbwrrgrwwgrggwurrwrwggguwubbwrubrwgubgr
bwbrrrrbgwubuwbururugwrbwbwbuggwruwrruwgwuuburrubbrrrgrug
wugrgwuuwgbbrrugwugrbrwrrubbwbrgbwrwbgwwugrugrbrgbu
bwbuggbgbubbgbwgwubwgwgwgrgwwwrwururbugbwubuuu
gbwbbbrggbrbuwurggwbgbgrrrgugggugwwgrgwrrbrbbrgwwbuw
bwbwrugbuuguwuruwuugrgbbgrbwrwuwbgrgrurg
bwbwrrwrwbbwbuuguwuuugbrrrrwuwbwbburrwuwbgggugbbgwbbwuwbr
bwbbggggbgbwgrrurwbrgggwwwwbwgguuurgugwrrrrgrbuw
bwbwburbwuurbbuggbwgubwwuggubrwbgbbgbgggguugurbuurugbrguu
bwbbbrrwruwbruwuurbwwubwggbbrrrwbgbrgwbrg
rggbrguwuubwrrrrrrwbguwubbuuwrggbwgwbugrwruuugwrbgwrr
bwburwgwbrbrrggrubgwububuguwbgwrgrguggruub
bwgwwbbuguwbgbgwuwgrruburgruwggwbrrbwbbbuu
bwburbuubugrgbrbwuwuububuwuuwwwwggggguurbw
bwbrwbbbrbbubbrwrubrgurgbrrrgggubrrrbwgggbwr
bwbuwbrruwwbgrbbgrurrburguuwbwgwubggbgrgg
wubgrwgrrgggbbrrugburggbrbwgubgwbwugwuwuuubbwggwwuuugwwg
ubrrguwwuwrwuwbgbburwwuugurgrugrurrbbwrbwwwuruguuururgu
rbbgwrbrgguwbuuuwrguugbuggbruwubuwubgbgbuubgwuwwuuuw
rbgwgggrggbgrggwggbuuwwgurbbrbwrwbbgugbuugwrrgubbuuww
bwbuwgggrwgrgwwwwwrwgbwwbrbgurwbwrbugbgubbrbbgrbwrgw
rbrgubgwgbbubggurguugbrbugguwuubbbbwwwwbrggrugrbwrwururrww
bwbbgurrwguurbgguubuwggbbggbggburgrwuuuu
bwbrrugrrwuuuwbubbbwwgrbwwbbubggbbuuwggwggrbugurb
rwwrbbwwggrrubrwwwugwrgwgrbbwrbgwbgrgrrrbwbgwgubggb
ubwuwwrbgguurwwguwgwbuubwwrrguggwggruwgugbbrgwg
bwbrwbrwgrgubbubuwwguwrbgwbbuuuguwbuwgwgbrruurgugrgwrbb
wuwurbgguggbbwbbrgwubburgwubgwrbbubbwwbwurbr
bguurbgrbrbrbrwuwbrrbuwrwbwurbwugbrrbwubbg
wggwwwrrwuwuwugwuubwwwwwugwwgwuruugrwbrrwgurgguubgbr
bwbubggbrruubbwbgrgbubrrurubrgbwbrruwggwbgrubrggrrwgg
bwbwwuggubbbrubguggbgugbwbrwgbggwuububugu
bguugrwuwbwrwrrwwgbrwbruurgbwwuggurbwwwbrgbw
bguubwwgguuuugrwguwbrugurruugwggwuggbrrgrwbgguubrbggwgwrr
brrrgrgruggrubuggbbwrurggrbwgugruuwuurwugwuwgwggugg
gwwbwugrbubbugugugwurwrrwbbbbrbrrbruwrgbgwuwbwuuwuurr
rrwgwgwuurwrrwgbrburbwwuurrubgbwwbuwrbgwwuwgwwrggrgubb
bwbrrubwgbgwbrgwuwbuwubrbguguubwrwgrrrrugr
bwbbrwurrwrwbbubrgwrurrrwbrwwurbuuugrggurwwwbbb
bwbbuwbwwuwbgbbgbwgwbwrubwbgrgrrrrgwuwgwwbrbwburwuuwbwwgrwrg
bwbbbbbrrgbguguubwwwgwgrwgubwguggwuuwugguurwbw
bwbrgwrbuuwrwrbrrbuburbwubugrruubwurwwwwugbbrbgwuwgrwbru
rbuburwggurgrrbbuwwggwgrwgwwwggruuuuuguwwrburb
bbuubggubuwrgbubugburuwrrgrgwrwwrbuuggbwruurwu
rwurwwgrbwbwrburrbubwgbwbwbgbrwurgurgwgbuuubwgurggrrwrwgbr
bwbrwguwuwbwuwbwugbuggbgrrruwwuwbgbrbrubwbwgruggw
bwbrbuggwwwgurbgbrgwubugggrubwgbgbggrbbbwbr
bwbrubrggbugubuwrrrrbubgrwgggwbbwrugbgbbuuu
bwbuuwbbwwrgwwruubuuurrgrgwuubrbuwrbrwguwggwu
bwbbgrrwwuuwgwuwuguuwrbbgbwrgurwurubwuwbrwggwbrwwwgrr
bwbrgbubgwubuurbburrrbwubrbuwbwubugrrggrbbgrruuggwgrrrwbrgr
rgggwubbwrwgwuubuuuwrgrwbwrbrgrurgbbrrgrubwrgbrrurbgg
wuburuugwrbrgrbgrbbrrggbwrbwrwuugubgrrwugwuwuwgruw
ububbwwgbgugbubbbwrgbggbggugbrbggwggbbwgrgguwggug
bwbwwbrugwugubbuwrwrbrugrgurgwwwbrwugwburbrbuwgrwbwgbbuwrgg
wrgwgbgbwugrburgrgbrbwubburwrrurwuuwrbubgurugubgbrwu
bgugwrubgugbbrrgwuurwgubgruwbwbwgbrrbrbruwrgrg
bwbwwgbwbrbrurruuwubrugrbwwwrubwwrwgggbrwrwbwrwug
gbbbrbbrgwgguubrbbwugrrurrbrwggbruburbwgugurwww
bwbbwugrbwrgguggubuuurwrbwurwgguwugwwwubgwubuwuwgrwgbrw
uwburwwubbwgrwwgrrbbwuuwrrrrrrurwuuguwgggu
bwbbgrugrwgbrggbubwuwguwuurruuuubbwggbbwr
bwbbbuwrgbrwguwrrwwwugwruwwrburrbwwrgrwbggbrurwgg
bwbwwbbguggbgwuggugurubgrbrrwurbwwwrbwubuugruwggwr
wugburwgbwwwwuguwuubbbubggrbbwbwwbwgrbbubwgbgubbgbuwuggw
ggwburgrubbuubbwrrwubgwbrwrbgbwbrgbwgrgwrrrwbwwgg
bgbuwguubrbwurrbgbbwuubbruguruggggwuruwrbguur
brbrgbuguubbbwgggwgurbwrbubbbbrbwrgwbwgggbugurbgurwbugu
bwburwrrwubwrwwbubwwguwrguubwgbuwbguwuuuwg
bgguruugwwgburrbwwguurrbbrbbuwgurgrgbruuuubgrbr
uwbgrgrubrgrbubrwgwbwrugwwrwgrwuruwrbwwuuggg
bwbwwgrggbwrurbbguburwrurgbrwwruwwuruggub
bwbbggurgrgwgrgubrwugguuwrgrbbggrubgbwuggguu
wubgbububgrrrwbguwrrrrrrrrgbbrgugwrugwwubu
bwgbwbbgrgwgrubrubwrrururwgrrrbwuwuwrbgugg
bwbrurwgbbgwuuwurbgrubbwuuurbwugurgbbwbrwrubwwurgwuurgurb
uruwgwrwguwrurwbbwbbgwurrrbbrubbrggguurubgwuwggwgwbuwuwug
"""

TEST = """
r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
"""

# Each stripe can be white (w), blue (u), black (b), red (r), or green (g).
x = TEST
x = PROD
x = x.strip()

# Data in differnt formats for quick access
text = x
lines = x.split("\n")
grid = [list(line) for line in lines]

available_patterns = lines[0].split(", ")
available_patterns = set(available_patterns)
design_requests = lines[1:]

from functools import cache


@cache
def can_make_design(design_request):
    # print("Checking", design_request)
    can_make_this_one = 0

    for starting in available_patterns:
        if design_request.startswith(starting):
            leftover = design_request[len(starting) :]
            if leftover == "":
                can_make_this_one += 1
            else:
                can_make_this_one += can_make_design(leftover)
        else:
            continue

    return can_make_this_one


can = 0
for design_request in tqdm(design_requests):
    # can we make this design using the available patterns?

    print(design_request)
    can += can_make_design(design_request)
    # if can_make_design(design_request):
    #     # print("can make", design_request)
    #     can += 1

    # else:
    #     # print("can't make", design_request)
    #     ...

print(can)