Flea circus for the New Year celebration
Introduction
We are approaching New Year, so today I thought to cover a puzzle in my post. A problem that recently caught my attention is Flea Circus puzzle from Project Euler so I decided to give it a try using Julia.
The post was written under Julia 1.8.4.
Problem statement
The Flea Circus puzzle is the following challenge:
A 30×30 grid of squares contains 900 fleas, initially one flea per square. When a bell is rung, each flea jumps to an adjacent square at random usually 4 possibilities, except for fleas on the edge of the grid or at the corners). What is the expected number of unoccupied squares after 50 rings of the bell? Give your answer rounded to six decimal places.
In this post I want to go through my thought process when I tried to solve this puzzle.
Building intuition
I usually like to build an intuition for the problem to understand what kind of solution to expect.
The important feature of our puzzle is that all fleas move independently. The two challenges we have are that not all squares on a grid are created equal (edge squares have less neighbors than interior squares) and that the process lasts for 50 periods (so we are not sure how close it is to a stationary distribution).
To build an intuition let us assume that instead all squares are equal
and that 50 can be considered a long period of time. Then we can take that
a flea can be in one of the 30*30/2=450 squares with equal probability.
Why 450 and not 900? To see this assume that our grid was painted in black
and white like a chessboard. After 50 moves flea starting on white square must
be on a white square; similarly a flea starting on a black square must be on
a black square.
So what is the probability that some given square is empty after 50 moves? We have 450 fleas that potentially independently can occupy it. Therefore the probability that it is not occupied by any flea is:
julia> (1 - 1 / 450) ^ 450
0.36747030733895836
(note that it is approximately exp(-1))
By linearity of expectation we can calculate that under our simplifying assumptions we will approximately have:
julia> 900 * (1 - 1 / 450) ^ 450
330.7232766050625
empty squares.
Building simulation
The next step towards the solution is to simulate the process. Fortunately with Julia it is easy.
We will denote the location of a flea by (i, j) tuple. Here is a function
that gives us a list of locations where a flea can jump to:
const N = 30
neighbors(c::Tuple{Int, Int}) =
filter!([c .+ d for d in ((1, 0), (-1, 0), (0, 1), (0, -1))]) do new_c
all(x -> 1 <= x <= N, new_c)
end
The key element of this function is removing new potential locations that are out of bounds.
Let us create a matrix, which in cell (i, j) stores the target locations for
a flea:
julia> const NEI = [neighbors((i, j)) for i in 1:30, j in 1:N]
30×30 Matrix{Vector{Tuple{Int64, Int64}}}:
[(2, 1), (1, 2)] … [(2, 30), (1, 29)]
[(3, 1), (1, 1), (2, 2)] [(3, 30), (1, 30), (2, 29)]
[(4, 1), (2, 1), (3, 2)] [(4, 30), (2, 30), (3, 29)]
[(5, 1), (3, 1), (4, 2)] [(5, 30), (3, 30), (4, 29)]
[(6, 1), (4, 1), (5, 2)] [(6, 30), (4, 30), (5, 29)]
[(7, 1), (5, 1), (6, 2)] … [(7, 30), (5, 30), (6, 29)]
[(8, 1), (6, 1), (7, 2)] [(8, 30), (6, 30), (7, 29)]
[(9, 1), (7, 1), (8, 2)] [(9, 30), (7, 30), (8, 29)]
⋮ ⋱
[(24, 1), (22, 1), (23, 2)] [(24, 30), (22, 30), (23, 29)]
[(25, 1), (23, 1), (24, 2)] [(25, 30), (23, 30), (24, 29)]
[(26, 1), (24, 1), (25, 2)] [(26, 30), (24, 30), (25, 29)]
[(27, 1), (25, 1), (26, 2)] … [(27, 30), (25, 30), (26, 29)]
[(28, 1), (26, 1), (27, 2)] [(28, 30), (26, 30), (27, 29)]
[(29, 1), (27, 1), (28, 2)] [(29, 30), (27, 30), (28, 29)]
[(30, 1), (28, 1), (29, 2)] [(30, 30), (28, 30), (29, 29)]
[(29, 1), (30, 2)] [(29, 30), (30, 29)]
Now we are ready to write a simulator:
function sim(steps)
fleas = [(i, j) for i in 1:N, j in 1:N]
for _ in 1:steps
for i in eachindex(fleas)
fleas[i] = rand(NEI[fleas[i]...])
end
end
unoccupied = trues(N, N)
for c in fleas
unoccupied[c...] = false
end
return sum(unoccupied)
end
The idea of the simulation is that we initialize it with 900 fleas, each
starting on a different square. Then each of them moves randomly to one of
the locations it is allowed to occupy. Finally, we count the number of
unoccupied squares.
Let us run the simulation 10_000 times:
julia> using Statistics
julia> using Random
julia> Random.seed!(1234);
julia> simres = [sim(50) for _ in 1:10_000]
10000-element Vector{Int64}:
331
325
332
341
319
329
333
329
⋮
333
325
319
312
319
319
327
344
Using the collected results we can compute the mean result to get an approximation of the value we are looking for:
julia> mean(simres)
330.6895
We see that the result is close to our initial computation. Let us additionally compute the 90% confidence interval for our estimator using bootstrapping:
julia> quantile([mean(rand(simres, length(simres))) for _ in 1:10_000],
[0.05, 0.95])
2-element Vector{Float64}:
330.538595
330.84301
The width of the interval shows us that it is not realistic to get the result, up to 6 decimal places, using simulation (this was probably expected).
Solving the problem analytically
We need to solve the problem analytically. First let us build a transition
probability matrix for our problem. For this we first create two helper
functions that recode (i, j) position of a flea to its numeric index:
c2i(c::Tuple{Int, Int}) = c[1] + (c[2] - 1) * N
i2c(i::Int) = reverse(divrem(i - 1, N)) .+ (1, 1)
The function uses column major ordering of locations (Julia uses this approach when defining linear indexing).
Using them we can compute the TRANS transition probability matrix:
const TRANS = zeros(N^2, N^2)
for i in 1:N^2
ni = c2i.(neighbors(i2c(i)))
TRANS[i, ni] .= 1 / length(ni)
end
Let us have a peek at the TRANS matrix:
julia> TRANS
900×900 Matrix{Float64}:
0.0 0.5 0.0 0.0 … 0.0 0.0 0.0
0.333333 0.0 0.333333 0.0 0.0 0.0 0.0
0.0 0.333333 0.0 0.333333 0.0 0.0 0.0
0.0 0.0 0.333333 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.333333 0.0 0.0 0.0
0.0 0.0 0.0 0.0 … 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0
⋮ ⋱
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 … 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.333333 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.333333 0.0
0.0 0.0 0.0 0.0 0.333333 0.0 0.333333
0.0 0.0 0.0 0.0 0.0 0.5 0.0
julia> sum(TRANS, dims=2)
900×1 Matrix{Float64}:
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
⋮
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
The location TRANS[i, j] encodes the probability that flea starting from
location i (encoded using linear index) ends up in location j. Therefore
the sum of probabilities in rows are all equal to one.
Now the linear algebra magic happens, the TRANS ^ 50 matrix encodes
probability that flea starting from location i ends up in location j after
50 moves:
julia> TRANS ^ 50
900×900 Matrix{Float64}:
0.0224957 0.0 0.0313408 … 0.0 0.0
0.0 0.0325608 0.0 0.0 0.0
0.0208939 0.0 0.0295701 0.0 0.0
0.0 0.02835 0.0 0.0 0.0
0.016777 0.0 0.0246964 0.0 0.0
0.0 0.0215119 0.0 … 0.0 0.0
0.0116632 0.0 0.0182525 0.0 0.0
0.0 0.0142354 0.0 1.18131e-16 0.0
⋮ ⋱
0.0 1.18131e-16 0.0 0.0142354 0.0
0.0 0.0 1.18131e-16 0.0 0.0116632
0.0 0.0 0.0 0.0215119 0.0
0.0 0.0 0.0 … 0.0 0.016777
0.0 0.0 0.0 0.02835 0.0
0.0 0.0 0.0 0.0 0.0208939
0.0 0.0 0.0 0.0325608 0.0
0.0 0.0 0.0 0.0 0.0224957
julia> sum(TRANS ^ 50, dims=2)
900×1 Matrix{Float64}:
0.999999999999999
0.9999999999999988
0.9999999999999997
0.9999999999999986
0.9999999999999999
0.9999999999999998
0.9999999999999991
1.0
⋮
0.9999999999999996
0.9999999999999992
0.9999999999999987
0.999999999999999
0.9999999999999992
0.999999999999999
0.9999999999999988
0.999999999999999
You can find an explanation why this works here.
Now the rest is relatively easy. 1 .- TRANS ^ 50 is a matrix, where
TRANS[i, j] tells us the probability that flea starting in position i is
not in position j after 50 moves. Since fleas move independently
prod(1 .- TRANS^50, dims=1) gives a probability for each cell that it is not
occupied by any flea. Using linearity of expectation again, we get that
the expected number of unoccupied cells is sum(prod(1 .- TRANS^50, dims=1)).
Therefore the answer to the Flea circus problem is (I leave out the
number to encourage you to reproduce the result yourself):
round(sum(prod(1 .- TRANS^50, dims=1)), digits=6)
What if we wanted an exact result?
The computation above was still approximate (but the precision was enough). What if we wanted an exact result? This is easy with Julia, as we can switch to rational numbers in calculations:
const TRANS_R = zeros(Rational{BigInt}, N^2, N^2)
for i in 1:N^2
ni = c2i.(neighbors(i2c(i)))
TRANS_R[i, ni] .= 1 // length(ni)
end
Now we can compute the desired result (Warning! This time the computations take much longer.):
sum(prod(1 .- TRANS_R^50, dims=1))
I give the output in Appendix (it is quite long, as expected).
Can we make it faster? Yes, let us try using sparse arrays:
using SparseArrays
const TRANS_R_SP = spzeros(Rational{BigInt}, N^2, N^2)
for i in 1:N^2
ni = c2i.(neighbors(i2c(i)))
TRANS_R_SP[i, ni] .= 1 // length(ni)
end
TRANS_R_SP50 = TRANS_R_SP
for i in 2:50
println(lpad(i, 3), ":\t", @elapsed TRANS_R_SP50 *= TRANS_R_SP)
end
It produces the following timings of consecutive multiplication iterations:
2: 0.0100824
3: 0.0233692
4: 0.0586901
5: 0.0591864
6: 0.0859112
7: 0.1325545
8: 0.1639544
9: 0.7365413
10: 0.2168848
11: 0.3148987
12: 0.8358322
13: 0.3933508
14: 0.970132
15: 1.0085967
16: 0.6097
17: 1.1991987
18: 1.1816013
19: 1.3753546
20: 1.3954895
21: 1.4366169
22: 1.5130404
23: 2.100761
24: 1.6176329
25: 1.7713067
26: 2.4755134
27: 2.0226999
28: 2.0449991
29: 2.7817644
30: 2.1131792
31: 2.2949804
32: 2.5469316
33: 3.2688006
34: 2.4443849
35: 2.6327831
36: 2.5831119
37: 3.2663794
38: 2.6593901
39: 2.6381515
40: 2.7143964
41: 3.5960801
42: 2.6999489
43: 4.6299449
44: 2.6266897
45: 3.086147
46: 2.939075
47: 2.7210731
48: 2.7317749
49: 3.2432152
50: 2.6385131
Now we can compute the desired fraction:
sum(prod(1 .- TRANS_R_SP50, dims=1))
(the output is the same as above and is given in Appendix)
You might wonder why I have not just done TRANS_R_SP ^ 50? The reason is that
by default Julia uses exponentiation by squaring algorithm, which in our
case would be slower than just doing multiplication iteratively, because
TRANS_R_SP has few non-zero entries.
Conclusions
I hope you enjoyed the puzzle and the solution. I tried to show several methods and concepts that I believe are worth practicing.
The beauty of Julia is that we could perform all the computations without installing any packages.
Happy New Year 2023!
Appendix
If you are interested in the exact fraction representing the number we are looking for it is:
1594916209119333279277969249244834228152875163677
6251627308610309974602655007725935456430277833747
5032114412680346852027982556518161560427602079062
2980363821401845440203734684558041376621491334524
8480453760106065213319719152781581944013496218303
3324026228742213240767118408273200426409457395905
3259305972353085925030632317592370199709926747679
5163965348230742219520453869528327241503916701752
7958656576031542664199300321190807312040176225678
8602649470726805576498417540870426251929085204808
8264285469645465926569179236632298386509867712457
9252520762839368710329829821669328430611063152424
2870921332144843166780913819578239875043474333183
9667493193454163578545023664993459606760025809521
7591997522415184731455074659022022666485556962907
0617036923445844608140197059224164147430976197240
4758034658658105156940633161821995308140304104240
6587496273606310576072409516632443948112270083675
0306298428123656851818688578331387144697753827806
9029546039365862220989593884819977956369097585696
1683700929149172974949556841723371780533505215087
0115928916866575781578875425874273223139721956399
3252377107173657011338169756221698332317844745294
5906977269512285867173046172846611612371016468979
4187468918934876158274492099438949089629379569523
9878173732409250236787246817768434629788637579627
9200058619463790080778631420163026731019650612511
1268430848907342258227486393684970848372825945123
8572525008101202931590047024592764202123687929423
9293706066441191608590730025192651294842915955548
3882448273671580479296429500255634403528978881202
9949166762080377636989711119696222994712054477692
7748295851792211157201373219956360350683870143774
4425973340173528025397054612843192755948015300598
3151486837292048544369405564992295438338399383403
3221757967845779443491949352210279067457628856947
3149424761755167752804873112856153016583978439095
6389469601018599011814111357828181550751733630592
9285647852389110378459837109139105618606555810427
4750921797165961018955982988002614781533387607211
2687841158587592820092616300333764788200754508942
8031201598227309926760550319028639812264350842226
1979355583215037507461648243232521085324904489891
2114487350324310057423702149306562034348670309026
4827260556403934442058014641531314741942757254650
5297512565576083893649343084784777165749033843157
8075672705432281544341939731637434394524497208358
6715319136361454011966947389800661804881779392199
5452598724653010654023561774773763329448426273176
2127728487123950059268615767776205515384681050347
2682930354944818636528289438702651565036003376349
9776749989989588510550428339370938728234765083637
0003564914060874667639696338462422162676345259675
1275071720648590704048494501963149558867491036195
6509654323020271599939059299836559666110116685830
3776518418630115292873564688436080563705411851792
0738221819896785355779305594822421758247838909124
8533712202715171922772372529480603065427422901874
5645241828077255346035338472240795595344701467370
5811031651527497641927120305515366262540186075793
3042728606646124397477644714024170294633272528701
3057297403742107218803035867691026247629686680319
1466593450859942823191637858831903635581527808634
2207803198125134676539977407874558797070966629611
1543436910359212009384891137513143441927307288181
7967196203562000885526772313318064810296030515070
4090648464303228288525575534678486313061130545055
7182314318775217110219012244104971951851660980924
6148721247250930902297601888456954156223840570863
0259111453711483312949513479676503540153160453922
0466710911081541620263571598598706210375032281725
4516515538140906492158228836747529269807835331521
4990998581607087401796496494505382887040455387517
6977853651951906123653837144237768913819460099307
8392516186863166935226756727546934468666487803975
0319010416468821343285888740607799295157102477707
9745964992868074043001196428017338290517555388563
8647956212476351528812535288386373768334287485180
2908078417450220887351250490574296981936363536725
2938208634889574221932146427924237706174330528406
8104911374742785282279509148635382358480761952587
8505078457933636084771556055037780155028492777530
7621675212947450060657413978853605276667193549777
5169905889674410693260971703726448173460403481809
9794777402987008114061024371661885849842862169066
2358297415689920055817517263083655766216471475861
6941493259814893052921624029662220713390371085533
9795234192823914567408555521568219629186832729051
9655309618863274963844411564154676537979675559148
0801925026345263736100481796804347674286372148634
7428990271541365967437153133406489639663056745098
9416616900390884198246448783248547381907611628719
2513720632520366580132277669499251719841029611658
3170051478153118268745437227091974393090650871560
2364425755074161701397590853534354770789310500593
3080157791929316886028980045046188290439853375868
9321279140644274681059284863651518203902470113424
8602553869268967021112637286606473507636351358115
2419771869509657659322010406655800749424380961625
4272426280274669755681675032138996189176309829271
4236132977283855649065029819317676326159342263774
5153790528617401308879324857674076027536622216387
1344234253163497539593166524483536878165135603181
7500135525149289374979298113270191967514666227075
5150320041151034855092839505635545400455436369725
6540828808729513611738084661155363366833096119968
0245778936008432249520715875549087183441506071939
6311307803736449361746769631380851542271852793847
9783147914374674418164558124557576734917154320193
3342964070063730673562422018418448326927198696315
3050342073717311106244878578542188782783362756275
1900650463352523522720574096063831795802999270082
0972767311411308280059813334199233707492199546200
8919128580674645236497872479623632775397610768563
5236918453037909591801412687837073255392213201391
7747150808821255245099543172913744339209893121965
7686036994782947164781118867612529467406708127103
5391021969667966652128057620557278609689837013866
2277923266690522715485755201464505456035177778325
4535174458019746219136892710010375942414807915413
6009088571155152445432059236874655653334406298353
3681384619107757011572134805285013933234109858318
4284396295637493401515044778747731833209344669773
5813035670430616835689817133944049265052368378871
9029468414051188091580345915889990258337560461459
3740964435150783292985231713200020819738405652111
2481754250293288249113999929295922655670759686820
7743958051942073748119841372931521847865284280970
9480706599853381346731691238668320067969063999707
8714906728042593890201016378036634931819879665932
2050523613729735974466755475639044211399205336085
4305418564150974507393380824360225925890368064506
2454711835198454796127288067082733681734583323641
8178615712086917206008078595177018087110465328028
9957351625182729900951801661734292599675442994645
7513824656444828310784607892014694660400412866671
6117729768394619902917958684708673053858916215619
6404877376141641255102840688280725412165727397379
8593259429759908205402736000685310849935300991478
9195731686374408951699153633312622669782142444178
9174752290827811466905181682019607129055636827212
0503785814209185183087390101011647980004827672171
5827678690909807442375347585322090739767067543053
6638588230741944247058003343749973516135803043644
1592878742687923696538883449475593338734613428432
3539763319680590185388693546799213323439985616740
8841187691707381904611361708293883027003231626933
6997275739669225350022012300876685308273575041739
0014639977982546911200908200777259174754144135042
7835959802539985154191670247515707072736513668098
9061610254363842677636114733381719083084346642144
7181843270427778030077382671080081111876013327222
0919326368772756428216259547959852098202413818359
5164322436076087193426954740975275235948836403785
6079197397398355851287498898809058621221055096005
6332082465326887829335761030292384880129797340249
2916092087922675188111453880349182894784501122370
6214504891973731065910930838495094764146467674005
0784259679169177026934662212905530127116267752577
1051552222998494220273194474332517168226195539053
9369542956785414345312134522062695640024029257727
1729072615214633266240936202028568496275232606878
1425113426293120523201475488483010037986107628455
5131109781026020239638291769506084886683956419318
6143558606378013877475024617997843663557047723359
0288768709398266697120347674171920482768570487834
6017413893710869920013750259407550764503821952200
0524908565032413138107011786002462277910343069427
9110445737091641032248989466431023103555666997868
6535598760951510473653986494869187203694921549425
5883841357424990669088967356723770922941684950915
7778869251706655807036292480536137112233541833401
9446861049059310764040819942437297244279161211536
0157709499361866392134047336053705772853070824694
4692023806168829509564847751529388061049598161667
8563939474687910609969763447106700300127038952765
3315914237926168366628308892967744925055023096395
4960883197162173409864478926759840188538806447391
7718509034901395633358835910253786944650994685023
0551020585620214801006043588824866454243368037323
6205307809084754728154242184686565301924399723358
8857096244754834326497116913363528884027619862246
3470917930098217979272366203114243257489189398478
2350260644449918348687540570252928532244443356302
4554618319184885478544325935126630041885929559430
3997675326010930481007156865685542948090574041896
1873428417327601304757469724326471152324173977738
4596733955479710258859592447952512503278488823689
7505168046688564494038349892618676343027868688828
9008795828508154388715420556536016890101750516569
3535023005099661704902769607704610007704777439473
1109482091508948405145147086406097109057758266877
2325410169650272273952550638599357252728511716000
3600065672967403332395887349686085009569673208565
3382831525372474477405143646858466511155121369707
7177975041969759829861147707941282664821656431874
4896666815053428396334193358197556906604057878514
8527878199841152998118457803020047172215787494759
4150670746582992707099937328949021381642453241322
6850232538834984410217345406880899949892451408733
5754471378791934699392892039662469312903648629283
9490284907882430936101664527906107801862266938959
3228975131881149164265471945874165851157628051260
1328530035127459181927004075042610373343147804394
3711026657837350756354320447568732003137568234467
7753073298582087921656523399557231618555095884825
9096965257079890237372992591250855438783174345292
5961148992419788076033680439805125728397586023515
6935970320948467298326972432661347403848932232454
0409721798180735907901090515025003451255494001584
9979458430598704955428727529101054555267405756855
8887103940233809738707103076173498968777680304041
7690943212442606423192253630164981666604417093607
1277170407658938438140372482407676838992905934356
7936203797541452680848164094676347285207340850039
5366567489175173130788264326563935120149937746915
0840462275110594209349419247266135268349675530081
1010848496116024628326013510157212440498572593311
1381251455699704068388540948133422758058022400007
9666041923321546682845217735608198740378895695465
7956355195591603462043460768666126646006232529752
0773246963517274425146444248416268691995000008170
7699373007602831942883446489706107341416270265077
1864812213808279340484978681691894744896857574131
5504004667695282954884117489034700261159184731324
2742113169469584421358357564656232446546864476615
3897344519784409882696792553915421418103721090125
2321027566278258957227380955164117310649317613986
0543655726047323529711510511295562433698499496230
3788435475602896041886769835034103170783974213916
0172281735823338210304601852311274048171936696148
1953371303587164210968026008218387185219403188156
4878786875828342456442275338220130331371646187336
4774960846607234550257472223758266825639166799679
0696967672260874859786480223247552822592233836457
4408922470502625849276751322885222467526770856591
4384036993850114375566703991423788727705164794339
0145762443681605747052214398893831907886238911727
6627043195008940105780706429801983189055396443654
6322885847538672566335563153822144792908194716499
9230845830454852987586515382703447773320986349674
2260477557704519374506600714023861302361870819446
2793264911031863196315417438083907419945808391143
6559623999046827242110709062512932610758402297543
3793230345149192724191548790077750901027181192676
6745892847932518200104041142302948205495145138503
4549500786504814579295019726546970214095361411241
3911100530752031497296675920842001316014583133287
0140956821633533162958144174974630560272163991837
8193807086155469851708722535873301923554480874745
5554874118237975112223137374431603131163577665492
5258195339992996928695304050876163201971140130268
6025948012660606865284372299171265505592856768425
1124869200117101349595703893383831246725137730869
0911747539833388741152701946809622864135540448100
1200047807604137691428209082620359446344391808895
6564311292317673708460518348372015108571521236913
2646269439466918607955808565126349083998721486577
5399205701704594003706896190969257417039168018189
6523790223899740431048188599011820131678384038287
6571812322316865604204359258813698746768843447466
1453690186413520773579303585182050688102820191190
1603537344756724210530651106562656540495403475627
0819951457983846118487020193234773101277192395204
7421875271475004866983199758459110765054243106087
5565696118956003673463172072063247274513357114090
3354442743431094794896281925703028033813299315176
5941081791157965802997858567417577950352171779526
2666579840841894116204909181500589874402482620287
4551306864847314863861550057134544769461188098253
1808028758525173110908578205293708239901728447641
9426005859746188758571167506301018599030327347053
8855966834903689237854546088725956237489343030085
4918418492722649138398268161926806701981399011985
9947561145607452048749826875131892701083709751123
4414316481110058982662234830077776603468865634273
9375579075308291616999324885941249425584865182706
1633627555547861154977488191233453149816021903019
9768559235399206970049543924945167930040194443674
6420368102573649583496003089671129857599360682746
6590174404186216680826417439526455473822728394975
7680858778762363371257410027693255322355614268301
1321299481736665811049773482971585298016798955909
4592921349553972507573911661392851432407664718440
3894278369423694828509812749670430440830990987248
8990488476037077806860715636309943957173026846256
4352017668500756987433222868643576355577494817978
0841989191202361359474056055744689731528447291409
3428164728554909503047319451390220971473215161539
3152497565941722232674914350590767966609375996990
1047907929758902600778838415742898924118848057988
2610187849836265281413886346866183153406802629699
6329477920551035034241586575868295480042589428708
8986629295367988435349191033883597568174770665759
1301986366342023159348864761579157852422107511488
1441572616467853403445712203100303633249501641549
8154343880847730697994560951250846879309954161534
5098369937116272019303440287314621357706520155724
6185397262412997737903458412997040485202471341528
8343581997562844915103479196740525282361174723402
1050652712373528221434828076104505256755533339883
9350833092623646579709482189022825596267002379060
4988271280637332956709863750026711002976971146357
4103496320819187664091450953643863186318527037943
6683270725458236211462492426222645004809494060816
3339011473986180029748650524105081924991519442730
6044289229156771346240795975774580902374782404758
7025113530160844045821019974928527805067668605416
3953808491003708549379537163216768342479775930572
2208020845730120121929142718752667430848865437397
9261066881979011637864064377690530674238146984593
4098012983705116769781450124242942780485829126949
1303895203330934666879428185061192165479165220981
9368489721987665300253063903814219623673892980323
9862221073609134005624253565116531590146503300491
1942857512016098828469831940548188751962019542883
9990305761925303033181523507598559637511397597847
7520786579887052173425258569254088866534582242750
2990685700581622658857093951033124152210234119393
6207973988695723697514385491953171992361119885340
4358415296958739148696009904951374600183801746837
6310472379409143896479382189484880216866632172850
4307258525460251332393854025175984377303235849018
6948748122635639774303832084708051625377426400126
8761549936815877476027336479864239524797196527573
2739263750371667325573551281823215375092459089802
6274610079221275699246611553949264808484766187021
5518988099250279603713491557957541435595103605560
6005136068611938243756042250236430688126910385151
6754408346149166534288423109356962746103161125648
9111669544482546411592162125617384749953091245934
0291125433899068700575854669351491699347145684640
1152202301792876392268255639266113906779701402235
4232066408604984756247982627953040582167941050545
0049940708861768010558414224014555878594978772353
8121321685488305806594183160249261644110888427259
0969293916692138701228601483388586023338627696565
1110554110867607466529989503115196975975048641687
0781396209904740243274524214627011764358867424664
6884173133274061845916413003231019626937450962393
3385427507342203910806967320779925605992282656952
2146918921126784848897368067702898569796491933474
2229582978969930255293990549061561436387477515564
1037847529196793949659809466989243475026177845536
4197866345510326332325156343628681899796273662090
5422935989238104539266375423376234761953876204811
4072704630826469115075209387712153281777386202625
8538594214147205574007752924815836685105011661474
0051146379128368523928451493892275585319361704309
3740457583557781460960093818252974656352695507333
4972018242967775072845068390093861641938094503952
1999877613185976642768228355569772085688758096520
5465226182334910555056683203100215175724233270939
5252183882703146798694009382042397009147567700343
4496051864795666387177355731903821547764233268601
5340234172953094270192390283823288538013125186933
1003047451943026585770440708585089042857906443080
0073562596617206608988795548697982499492545305388
0084132246970970580131361298267667398750851110765
4756465080444219163534820704130261041592381298682
0989303754032051014570363190400538689004410166045
6957988144898343865635174319803324752738055996690
6789624511510620165357546018053576303130902439849
1800092052628289364424201259264912621424869631053
6603168460936074424915366507078340554326874209630
5448796481782115020608654928965977376229575503862
5526995302051750031797143153803413138915177875254
1512422963752587908037427152005401338774596166243
8230729995556938591240610641311831346998356195803
9674915821559867547227167081518121148686573211594
5071170190252009042602065390205776404700236190810
3055881500154165135990119434303699747250506294647
6151147535371306335142562963368624741672452444332
5918925167981256106081581205710517998431364178143
4900842438304297988909692147119850911696940695124
6100415295088279415307123362118449274725149323640
1776902985045791200097618092459824962189173371966
7284908182207044052679444183691037208892236808124
7475930876867459242307953958150139597361907887419
5376258658872763150597606754511165966318779969180
4356975576652426348959047979750648607219043334414
1867591737608023570705744320925769858419507760023
0702212721038974921999353180631833091866252033175
2508720775200125477679565190635528841797413830483
6233098635448624548955861989352875475332359222160
8964118936294444093291291652013734843287923880958
1014734991219840840466110466775835231853966726756
4924267107009519771382727186647533644805527585598
3165405049540291555415784389270813812754627554580
9771283258617705394863593333189466495428149904013
7719067259305924335597320261512184150999927605652
4611705470051275905154579383176477976796110460184
4711688635238367635862918601213211493496691597752
0002307080243313935564929848212837595461041499545
1838823827311110536805186868195016701245500358782
9981831702322544784382920702506608851974434511015
7614324937231828457109873848379242302663413575904
2328470185230945584572359571932819047936925821876
6680234424688436445728492486997224372314092261365
2038856127245742778793678903959648587559146701875
6410717709149358564876966451789641569266999803935
5381618817231156511046121187619198621165236257637
5091920297593031080242896047918456261913759957981
9495907845275050037202621953803452947257759268838
7473928547852166794940806162834243183223017307637
9637596468521858230788346355903875111218011008963
9612844378786852581654424904656800455110504859918
3255096919360701723713313077697986700155740861591
6208080090207596219665652117996406171932137849368
6535231845725928102063803858055278497151380917705
5469614306494731919477932513416918928494435450247
1436577809339684656409117484808837784687438107297
6560462188516260258500140145336551614560179605753
7237641470995500242754859190887521294293115771236
0275149485694667778992246437483782414189650536987
0169098547925822473937379323500963374472701111690
6630861997178065214352114729207264756926445677106
8015250455911105106401830613873202013658844877490
1768216341767817208730404514613566167710869322771
2832727381817089822687103553420630679825244620608
3964082810895053472863555894450471325231864561538
5068655533023196669496076436000209767551875833593
0751529729930082342086375818286586299950923400178
2174677296969437145277650670440690823892814723823
9668317863212943366427483188338486312306242311962
3545736367849973291130232326581872351386528825766
4731853834501655175399668797322926605146730447770
2663148115119603346518146081791997700429628585361
8262781728027057078578140098036927155790635181736
2441888394136649836180601394355471717912287579233
1487722297841560726683029808136191142799773682481
2724506795139546795248389538259156954821371094739
5549186838640149325207953935493537465550330392370
7594657405222036247859363967231874296045678568727
8010145759894434667813595492013527182549640532750
0269034411354830615103720922762830510897749501897
0881103561653760860297594362935700341170737563994
5095586056731728657666754603953801027912759603348
5718746606026387639301621038626189520725803514165
3469658539822057804298191530101291846222011372447
01385498046875
//
4822540650211477972869083601017442113987952205731
7288696511159085418080315787649464285320642056734
3086087465204893941804462517572177676717237383465
5489953229997388089275625468106564246715413687353
8728320661518274246550462682072938769746194292090
1029411339165140274161529145770409135379210439532
2875942363334306963769596903983142208646458602491
3365992747050443300294436635946802669771428031582
7917421101372571841673007759188962300570752922096
9866723929822448157277653587315842473780699140035
0798710403636131453726557031872586438348256983016
5905039807523667715499421814485259080128254340652
3716805189800115093506885195360281648853271792400
7011666503592417514560714070313317226133572614977
3590261972636744417455732382568396015376778740354
6643920729083023013135062299103679388218131638097
7191414716296245872337651396053332951384711197735
2979075100048479396658754512502653961368598105931
4341224610192779473328439892157779710375886216975
5088640019453729278097094302283371317810786238180
9251357738561699334264630100893399081798073855863
2883950511196513418826063870335807842761783929391
2094071098912962386570772133091945880809971686316
5281216280269945979627934984715649386198013981679
3001691137357427657533327369499155969429705948329
8556790497499704075435556460432250308267831052612
9297940839727862663172305862321138412614932596582
1142621154548983648218188231560278805082562431634
2725692190904269639602957303011078151483770527302
4908839521814544094254829404977884023896393457101
4104574181736785491089608731495182793014719887160
5773803805817719636756477093409060550368975404471
8293350270764096233241691343050862067627798405860
0751466207779551477057859364732927395292508078026
6435186614143214100480849240660857274824541093045
2290590841883286509566717791329510326752725340028
3269669328217111555864693933131002041949223735894
3721564177676702717921601979219380325281074130929
2432594975782396232211036487485166597892633010960
0796552282896611747497916340136308626330926162059
1184974213463646153223278864423579290070432190971
5891317839883523012143973366031478258694801098584
1558288726407755910498375779527625947204523199136
4446659911222722831652924221653113094534936071295
3634668593812742400907367193601850877981200412915
8494128386952874524434129581099356057264237735986
0269404725399943219609921554735419212027695963102
7034672224173672510040529203111851059756535069898
0249619458315317746798615985494564940129837840008
9504253335350597350929503870194499954658501740339
1094257079111103821805753440789443788783784776592
5226836479312917063216152621773718697321501400140
8103634339333736806566698920503139722550435956940
4028034799384600708728720290344622244774412443537
2082390517093545370735385815365289247566174122910
5818048136824179326021022539468325748657197404636
6661717903314864479614221454453209499371085354202
7988093103569182238411185496246541350036538932280
5864037611678920500768443142776627238140300135935
5005172273674105350359339353245986973775215752332
9560746972480360064655860595974603560055389369027
2277659329682320670070869930496774855810478370814
4739441086072152208413032094145228660018110877570
0765474817408098385405577324063515533442390498099
6794575874790479271275170946771410985406056892519
7768918476928181270508359316853848161110330117169
2601614673576194549573661225083444423881603049796
0985526562669102237931998506555971251634691440265
0877827974999816487155579380590837954770522456401
4482076402901169804902796300614724254101972562741
6096621602694856710863023983297588841414513485855
0073553624692146326262708756884577383922014266485
9003566148444162759792857903784693994516491703748
5741524019747393998282053648908760083029782069441
2090434708671120573374057218112114874420034125560
7950121054129912304927346567274553665727516865428
4083636050895819459301681024086284659236496287946
1021159427084194571861796536429669325283872636248
6360134441952107357901162029467425964705142608984
1439289499436425657651173332083937418444640968834
3082102969462287106902444178116203045436190076410
6348338728926304369329359684234942405114186834767
7208308877596373602979013270248035341770258486663
3067504012029017854964055856546471735110774919431
5833544199606400066191721435476752759943840825150
0351301857244827620280620381220656921792447908282
2003998873056282398068997496271544984440318753466
3525458946051320552908398677358231769244285318461
8876810426513705494348295399786299281853390351784
6398360726463042230436524373913028412641103765989
2034896395402856531129199502533002719261291448210
9217475913070586018447898258948176481619306266104
3468943267684369357485896023654456025924259381275
6171336583161902460892969787953545004797486367304
9203300937914731645932102306766131837774326434607
2737975018410389331959722387903613927674560625602
8194641878576045961776686661291475787620052223235
9666822290804809063743857162110625077484482170003
3684427572258679449254291182891264268539376058202
0989860964007356779831672128244467374814978904428
2613050278500132523167332104388733274651363709996
3552055926769493185484754336960063205415720249001
5012423209160460442478506639874665069051025114119
5900192888598024764465998042042652783547791868805
1315214922923602431311874143812970952802802426131
0051994911158803712242000651935195418115985836863
6604388448263161028311819394834166281362100484368
0314451573743582043704466953666255687200881190186
9608394781782278890654522780143577370672670559448
6253550040463720298727404107341310079014244449720
3172077440156022858836305940836217992696475617803
4452426582885108693041062226618463733773324069830
3275839111131398496083007010963443248136845628381
4149588545935815122142777160584807468490591683728
7707602671787869295748297021726306087512349501811
2757512334609715819074980356706135918105787691825
5802612143233197577473945792190601014809912381055
1315001665850797884231515284842611618913121363563
9991382706953176071124859879193336107567658134222
9061720889297895600620703493159927792762858751431
7674639272142286514595653003556381798937063252629
4100431649866885903788542173890901747254260110229
1014651702247272929897597609608559572972311891773
1873395627509667402267399301564015986633383820921
7210939137076395412041481903405513793798929128761
3893217904672945620428113642904593060111134907869
3003122508850305361367911231613602515246053920785
1456250849274980947521708564577833191425620781314
0427104974646247565021536322097419076566504688069
5121695519223303805939403311724293569708113830994
5170551405103818544005557742285669096512647493962
5813766987601069506267686576994807319514741721572
4132700585299157116073810599584828474993042607454
2080399787768433352026321652110887346223232703862
7654531502404012247978165282293397599835758725886
3849117722205330095885682744027532042016315988416
5864988083559323783876207988566875528228878005719
6933218853673661636365408852641320809702707135451
1819675041368160106239081351453643136009309206482
4600678456051765539047437848201170736355312781949
0362333342318928595027398964147846834001928073479
0366011009779186747335554848073707394956273305792
6499379828446117269962526730217611166321880083492
8778812951489731691298946666500841449683975883967
1302984968385209586685687094232408019635303619206
6451394210989932751085758259103824564866199720951
3622224064522124785356009756808352773089141472542
7442120748932115592182862496199325858928773100308
0317288970613308831152615725564815052918188523594
0980044078715581444730676581137572004168280925562
4242122127343412600018410556443729667941306061797
9421049499221694622036381144593305740215486094576
4802558216565283604206165741138209681110414155725
8484265765312051612589859836830330737633935879587
4087144368226865502119904239343524915664255382374
2529651228229945073657703457817000464948380053092
8893904650772566864911844808539902881890761509687
5225176890544534111314527104159766203514166366002
1647758770835931975222561697576448181869041201343
7698823260963025860628551028224462097160492392350
1802941092524803735763119334575931382942213200754
0971958170961915770695276860864686885761961049708
3022578822038152249479712455463653992915969803217
2272162074893316844021185617299074534066995272075
5542726744214189680452667103976792920294037204138
5391573861902643480910441100797086961588170883740
1086082173725569579771884384088291997654716538188
7390119136810269170162862378536450840668520948470
5541142745426978740933403916869117876044960744794
2584786723065782893840464745479253623697250740599
8375310240803419629384038714598327493639246465030
8592302477464496432532797391596852868646129438625
7595037157203426412432788534276295602669091858098
1538756256032364546808008486278084488768098706137
3994569339275987861932985762709709678469748095347
1656017703706162912271420409404877261842334232535
6438425485820189878738563555753716454428424773581
8927665019147066373468272679137871302617743794757
9836235076783352935113534604454979725851397410293
8445979957892060140329409742227452281030941816305
3556103068445965520970512219139256713427700411722
1110935425118825484669927648232005714088250979069
4968722012502585653447943276952509466627071986958
6326552027527178564355167959684648273968423211986
4590280479062105208765819073533808516331656496519
1404120200338500446260610255365555113486844301284
9762895950737491380374969776054663678418052805766
5415980078959281694682136666920650455090603868945
3465017544612992141540042544625570496879158358269
3939161728058947888114841913711492156580845845903
5465102819173595135418221809067077774635838213909
5819863909961310714249082620942216456894102523351
1263684683037241409612151195528459731258815124766
6937140840449514897483219592642917951382323863169
0449402768446223724681099063849232211712971840335
1196260275019854695383724897447537012512270747311
1781289187672781122610351096788831474646734054256
8406376225509663296772067499849018379392974168153
3264920733424019271223102006763099508155351216304
6933578239899813764514788577143638035469098006639
8723786253447703728731378432694731736744659259424
6149699248230558885526089309405735675351894240042
4590290056540338456549620862154393568624887638852
3956589303577815876242818142338405153614544733234
0959426666091234982276588424672545296099921025829
0613139365048479199600876576410621979293475797708
0340504948929048336682888737198284296147855849072
5649832474174427903516560547060110685601535529123
6600979483664401572901912915318935200498151504339
7079259460286954731423020933388561355731601421655
6920438057977952769507396005675846180998936223092
1929767951961164071220382045112322379318156941018
3958815887690533858457739516947358673754411511209
0864557462864176838421918433064422592755827268731
6559705445539792178821806892042906987067442918476
0693060913332232412783391820664215806179101486252
7723322824509245047605577927895550502741019287210
6236084457005297130015579554491954990588599955500
2858457416213558088380040254425914936366539021460
4627408219095289369146364830767455280924293268860
5778904919138081977720285658222461771425241581418
0949757962831510574433215350041314548474324848045
5525770803951990628375838838441055474082629222162
7988260433157147337438872954478113215163240014357
0502935461151940848442101376470241382648788110729
5858334995956681658438214633598546319926395263748
4141359778958390078913351942499020760345257066810
0038111268954708595079366484513698179541886074016
0156630187556105919912397712314688685133428779794
1277879394875773964435691729676790408592621176152
2547270828196275987070432130977604488094750480260
9773842570089880099274405582719510679339622390536
0799550347219802470289966655307450265090725309691
5041120329887670705983502153976669733002843777537
1624625400308405548866179592747832291970885400534
7006668111019403720902929326373218824035247485691
6704947182019235692745148281666093831937915769278
8244248502508192300809418043014716483237186939473
9872889076818905981476447153700311287309099351027
8678434601394247875308095121863396124948839577077
3437034764839570502199648060283751479594758349240
4680860135000651159818771866412239081719694402411
2382560838738103592420006365748517998254382992780
4088010896763056264725211763206104877901030367961
2568882751139162583245377675823210885115621405154
8953392307224741084751142041834296890690941925172
6292468424446568960613586250498637331486518725272
9157542177096575052929356498250490054064812644521
9924679643383158210396598642339138102076899187846
2698867267466428364813304138174513883613141864105
7670070645777255904498175669285725777319406732401
6903616407890780931459335316710384326003068696531
3863662671546819430638625060589075621981943350220
0497628102160269540180727594598832737288164527868
4726828858568639608914728814429059814774637698512
2572910699961518601214941991605087615090658403189
4156963687987465601310448110213215662983300400293
9483065594101489594498964918589538946243104898797
5718243753318657721529795049118129388411515374300
8151644588716637655654944811007633410607189499247
5175190067514135497459231764585181592212411776624
7217316011101215484593007340912287321222620822215
3783920834275709767679770134141817375385581428622
1023144778260451355808860736338144464665790273099
5147938169163567749196467956764912329444125611197
2583631475631756482256912179427107975528188001288
3142285839553585794307095020167743596074379995687
8659351404447749655195175584235923218684451712744
7006475848909689765506593568782420722510471607632
7162242804759948596530549553675632781306943228635
6515785250908810735459113091330686410046575632272
2746354739232288198729979661893542904694280725935
7233094210049248126547672501445737158446402895238
0393836705181809947093025157636963628908449406557
3823484454348252895841904635406070756738142688681
0704278541661480691268649910800954751876730750646
6985916202674255297335893568124883576966454696501
8951571838911980408940737088281787235519888392284
2668439449957224242573721150525925037024335786819
2665568827993812399101139118380242248393080830596
4161875423139648928529849803061036606461250275791
9342104956477175106306775019075884445492673967098
5553193418535902601877292353243165846656727743121
6680447445420082652412954631733703760810359396332
2813630553633459391005604643932933733419917089788
7110797627593165956930841840568958556862790434866
2670680103895630526567868102608612264024696733113
6941058303697769565773854256693895158765176968831
3286068255269274077697087403988139487564837296333
0349811846356936708029425226059220735379376100677
5552145867115583040164397516442272313197059843090
5818806508833719660900615582729233042576233006292
9911847064429027112144666042624005526068806561311
8019543872182594431691154436489218922266797648682
7964528818584113680285478160830079147139547935974
7134217963145196813095221665832703330191908486308
2065530748193500310056856009901650466177404206580
9996421419054811288343874436765202336047845521381
6552190030183916207984929935669514837799752546622
4129536488443158533318097984639897166614227933475
7640268771767212707979809413325323637605244988131
0241084442164552336055503951274852040320622458659
7238943255050811743502663341775027890563643172813
8942590476206458134710782905457523873365035421892
6679133662028331862761353606626681353266791077020
7791237784137330304450384383603594743308065294164
3914134280119730616713028896393512443098772201268
5499195057379656647239657089494080193053982298557
6301595248732665161405371438298452539400046832692
7971395711278061759207811057106301129351708816356
4287128126403735602835727879212506480474875699879
5536228446525690886279070406792411282667006074182
0145971442368186418157579534884115799803248631463
1181899434997577792024219649736814481263472569592
5334101109124969174675077045256474890396480998031
1551900728055215638375122281751423544564429541153
4014007944701674501109310337209269883301840692768
1900651631392173772717470564510801445602976057255
7515072384844697350039051870186720036418612578543
0419303453793365370448320483529441031073759766716
4617559597790622990042820260600745998503183559148
9075191483976694887155550093356128230103828651917
4045629348270094704802961217299415223557616769977
8518777786454737816357835498262470631412658248084
2429188084649925110363126338627519977691368232816
7718280685222845417006578251406135839657708968377
8377178608808637043207820165911107949757174903409
4567743212149819793080811292723345902563133493409
6055908967638652683476902675879301925995267317246
7532945716391600412606739772506269253703361490125
1845924692507955393296919717430639222212030392720
4950306980477807160635435696988261808733576673980
4972842095206158644714130834166032836507166904896
7471650768551999082416561408944180815963982178459
6228230103635539837591208240505424231436752007259
8500163041242554837662481369819342020234542342396
9227094923122800142541626054848773602676690426101
9059000881491428292136721483782885423338629589744
0826839938128895595006374198816739975743554997850
0756741938636263594423260097858476795804371243395
3325277237925150393476828728674283072043370726853
1571027037498152242519989103438242194747812355932
1571727363199214471242074744393151634921170329188
3251106522873227696816803232278608980879372447748
1064213460709301389928322441440056576558916892067
7626463749377726044749418022649304383780839693486
3797420775080326916062558451423742204426822849459
1114327183065819011199950372239937770111027840694
9790694347716129592827574349309866706372575916011
0932625876941816590404193853772316139953163465360
5133196576852668859682558704588313015385288279399
6807945444317552291082450768251817755351168269301
0474893204189323208536309189042716151485280277060
0932651274964638339509922665144549401024469065316
6756349071784421623616735304543792215855052748153
8776350400785296871293087796140208664313995314665
4781837208724804946336970955813506816827577722670
2440695819838039657810093379205047305468845157191
3688398994707179481327422567333230232304089927133
9500622186934945910953810280297926745751587724393
4668704054165330498074914924857581186170694703375
5547588864023766813482352175155634800606953344738
2433875923387246422009209409494957173154197347604
8558495373159764196276278459971828960142105739772
2963003733865394652551381758016109605697462779931
2941644382063452352092329528839444385314432640228
3982419892488257158379332005853142853087170603789
1888982331122415915857964534484440984774048100843
7528976465832370123107932157717054573244229094265
6097861255712392001465534027402423454448237377629
4989218571356191340502969938497021222697015488140
4391980208086900944011095710288737298208083923282
4079093897655699000063370245434593385369170663799
2596318521588641251092267362607461716766824956298
0836099349223519754616329524621473792598099618726
9239297312354079161427729545081585290637347862956
3118820242160358217230373595387513569619687160000
3539873542952259138885805537897496188116837936219
4604001028081162370879138320764659041779674751733
1976813423434302249715327209973753614534584901581
6056191062690047056064206246907357261962020648045
4141228327504686140866258713486414194958050239474
3873038654534183484397397858375572726005510895785
4909095435283312464408701324158203640148041563955
4923124533134487521797534209469207588608891593386
1271437740154022533461397924511068613938893999700
8640173444245218519588742174973064345655250487358
2618129842993502270573604905302443403465420978594
3758762239772605147978637547595930462974270168564
0058201276042228022569027803399685611952688087374
2488641769936007649682019408744834831310110739008
5759429371416412117050344271219823561078769066736
8487640753291556753669071600145955552417681698594
9494732807001513103560846827629335748241574477995
9287401860015126687755200162174397459101611434955
6703405817860553411642348721888280666146140659709
6185811165547765251926998008721936281460540355919
3534926399757232391591237137868890646261451481439
6519604355637729380597231917133405269225628742434
4563256091149612823973162675004566982887907973320
7061425727726781053561099694766867158618420674953
5326686399300094861665006763125487026004896425180
6552484439512997849246471106701864715908193935832
7702175120541491553598149404450888206426961522215
0159593580915220669083222553780065171847771595179
9206039148524367005489437138741798268202398785392
7788573088331482272773622843051014362293838977990
6282842012826769361006089362655884282368853875729
8025754254198347894277915093768274780953968696896
1006194606298889986598022052560604598641879378526
9776329510528513796118996166325540749437737114060
2446511028537471498402861124295905945167415415716
4858614009155511203533498022663914758990223133368
4164978798422727996618044634592634898947790326404
1983537695782294849265304938063205200088143319140
9964793754347741385955473414143248881489307201851
9158116205382040336762686196645408402157885909646
5801759025443361948477248865209562120630651048030
1410369710081385842238816988745489351862900126750
6870355141402420854933688974153930358838885660557
6557822452820279441854242317941078831132619303109
7024068644954812662080681942295620420952252079938
3079874359287747249655738870445125561806285170121
0703987831197482473672773375254157578349401289909
0505270813984618469056750994221660422529940371514
8482507920163982769496140062619154404366545990380
5447490205749432274223560751408722642098460318095
9276713009937982657809002049678859638143992962607
4894594580778590475299383309577738850361026520497
9064875815775102829056679456225788765226688469206
2375799190280852792974281071307949684724977656021
3990925150195223863371174627094497582606271332675
0268476595893044018613583217542786237414121637174
8715750986558720894469780761580714115866565974642
3173641460592019377660893908480480691997775878456
6833366718020202211514552068685879524710416811266
9915564352364024532226472648253409322422201905209
3316923263278573388483708185746703831953987329674
5784132375371968769256341082967367059929304131668
4101368713028812617965915538890325050361716333569
48723728384