-
Notifications
You must be signed in to change notification settings - Fork 44
/
Copy pathConnectedComponentsTest.cc
748 lines (732 loc) · 52.4 KB
/
ConnectedComponentsTest.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
#include "ConnectedComponentsTest.h"
#include <dash/Graph.h>
#include <dash/algorithm/graph/ConnectedComponents.h>
struct vprop {
int comp;
int unit;
};
typedef dash::Graph<dash::UndirectedGraph, vprop> graph_t;
TEST_F(ConnectedComponentsTest, AlgorithmRun)
{
std::list<std::pair<int, int>> edge_list = {
{433, 280}, {471, 192}, {738, 907}, {128, 664}, {999, 933}, {984, 440},
{247, 310}, {565, 909}, {700, 727}, {408, 406}, {265, 550}, {411, 899},
{630, 170}, {179, 57}, {733, 727}, {543, 943}, {475, 141}, {632, 394},
{859, 581}, {203, 609}, {796, 589}, {494, 784}, {947, 420}, {354, 889},
{184, 492}, {939, 587}, {598, 623}, {110, 971}, {296, 560}, {507, 881},
{310, 674}, {280, 274}, {829, 845}, {273, 673}, {851, 52}, {814, 902},
{995, 527}, {389, 611}, {537, 387}, {521, 350}, {849, 934}, {208, 57},
{227, 962}, {30, 617}, {617, 962}, {512, 167}, {325, 1}, {232, 645}, {676,
963}, {89, 242}, {57, 237}, {118, 252}, {807, 913}, {75, 425}, {782, 63},
{901, 394}, {917, 23}, {923, 686}, {569, 451}, {217, 309}, {54, 950}, {508,
185}, {642, 135}, {548, 436}, {495, 332}, {93, 368}, {483, 300}, {537,
504}, {330, 526}, {29, 220}, {705, 598}, {468, 861}, {140, 13}, {192, 598},
{347, 504}, {859, 182}, {369, 826}, {405, 979}, {694, 603}, {138, 269},
{24, 364}, {256, 442}, {983, 657}, {946, 896}, {449, 915}, {6, 838}, {673,
773}, {24, 231}, {235, 574}, {226, 875}, {327, 722}, {474, 311}, {501,
904}, {291, 525}, {410, 937}, {804, 981}, {367, 113}, {449, 281}, {390,
841}, {148, 698}, {396, 122}, {470, 726}, {442, 23}, {627, 762}, {493,
406}, {710, 914}, {600, 289}, {182, 684}, {800, 569}, {965, 896}, {953,
509}, {173, 25}, {671, 289}, {682, 205}, {71, 683}, {666, 286}, {414, 381},
{23, 568}, {951, 45}, {987, 833}, {196, 225}, {686, 689}, {708, 87}, {954,
715}, {209, 238}, {735, 700}, {357, 571}, {352, 466}, {373, 730}, {441,
701}, {349, 224}, {289, 890}, {234, 680}, {721, 974}, {698, 801}, {181,
460}, {47, 444}, {446, 142}, {262, 236}, {27, 494}, {958, 229}, {283, 210},
{191, 279}, {359, 6}, {166, 810}, {808, 281}, {11, 801}, {484, 134}, {207,
78}, {97, 128}, {182, 655}, {658, 329}, {926, 225}, {677, 285}, {183, 468},
{685, 750}, {200, 999}, {871, 48}, {832, 515}, {485, 859}, {485, 75}, {13,
435}, {612, 658}, {138, 796}, {919, 949}, {910, 747}, {975, 691}, {410,
123}, {143, 788}, {535, 650}, {289, 386}, {48, 466}, {625, 783}, {690,
851}, {761, 689}, {638, 964}, {106, 327}, {886, 578}, {223, 840}, {83,
572}, {484, 802}, {703, 337}, {139, 522}, {234, 937}, {73, 555}, {15, 789},
{335, 444}, {159, 468}, {747, 900}, {202, 563}, {880, 741}, {227, 307},
{37, 594}, {380, 88}, {827, 286}, {747, 679}, {351, 208}, {374, 482}, {989,
684}, {157, 691}, {207, 681}, {213, 302}, {372, 741}, {260, 231}, {710,
110}, {529, 723}, {876, 580}, {156, 344}, {503, 467}, {887, 439}, {798,
53}, {312, 342}, {890, 237}, {973, 738}, {36, 726}, {581, 386}, {153, 333},
{341, 992}, {210, 389}, {551, 194}, {402, 407}, {875, 538}, {16, 873},
{180, 47}, {119, 360}, {402, 996}, {422, 30}, {380, 939}, {722, 24}, {663,
827}, {621, 266}, {113, 815}, {887, 976}, {859, 285}, {527, 646}, {971,
190}, {84, 915}, {110, 953}, {934, 716}, {304, 316}, {413, 419}, {32, 373},
{730, 936}, {478, 235}, {976, 947}, {859, 384}, {94, 33}, {912, 253}, {277,
39}, {980, 696}, {91, 692}, {160, 263}, {190, 707}, {459, 166}, {221, 537},
{849, 375}, {997, 679}, {57, 591}, {601, 48}, {393, 78}, {771, 839}, {254,
485}, {939, 809}, {478, 167}, {881, 502}, {81, 317}, {76, 31}, {614, 887},
{578, 417}, {970, 582}, {237, 389}, {951, 228}, {783, 626}, {146, 834},
{233, 138}, {458, 861}, {167, 957}, {391, 619}, {880, 742}, {769, 210},
{595, 786}, {708, 823}, {574, 159}, {663, 907}, {383, 781}, {861, 971},
{395, 450}, {942, 183}, {558, 883}, {827, 609}, {23, 561}, {479, 386}, {68,
915}, {75, 926}, {874, 927}, {15, 344}, {308, 359}, {788, 210}, {771, 65},
{18, 494}, {760, 102}, {218, 602}, {53, 478}, {577, 476}, {794, 736}, {633,
394}, {102, 941}, {686, 188}, {19, 326}, {626, 42}, {580, 305}, {304, 691},
{569, 294}, {184, 239}, {698, 274}, {84, 168}, {994, 35}, {415, 591}, {139,
416}, {152, 790}, {414, 123}, {987, 740}, {230, 973}, {206, 337}, {8, 329},
{661, 477}, {514, 582}, {646, 944}, {32, 887}, {79, 655}, {749, 541}, {831,
479}, {697, 443}, {691, 497}, {531, 432}, {595, 315}, {440, 663}, {567,
705}, {710, 788}, {659, 805}, {112, 585}, {633, 934}, {358, 108}, {170,
381}, {360, 876}, {155, 383}, {496, 69}, {104, 259}, {579, 513}, {907, 90},
{438, 791}, {296, 322}, {382, 380}, {788, 196}, {667, 833}, {632, 598},
{834, 396}, {45, 579}, {809, 724}, {470, 139}, {122, 686}, {667, 858},
{860, 724}, {971, 644}, {838, 708}, {525, 660}, {94, 971}, {248, 531},
{381, 380}, {178, 225}, {388, 291}, {218, 876}, {893, 177}, {896, 985},
{930, 37}, {718, 804}, {553, 972}, {789, 952}, {367, 343}, {674, 387},
{556, 160}, {985, 256}, {443, 917}, {377, 25}, {113, 453}, {43, 271}, {802,
567}, {79, 199}, {713, 108}, {793, 517}, {860, 488}, {232, 686}, {983,
451}, {360, 106}, {328, 853}, {190, 654}, {853, 10}, {580, 896}, {125,
334}, {570, 449}, {192, 702}, {884, 146}, {209, 918}, {383, 810}, {186,
460}, {137, 104}, {144, 845}, {775, 91}, {296, 805}, {773, 742}, {2, 136},
{204, 752}, {370, 227}, {638, 957}, {192, 298}, {471, 309}, {718, 2}, {964,
584}, {770, 1}, {232, 333}, {836, 921}, {263, 900}, {414, 629}, {824, 304},
{379, 575}, {233, 160}, {547, 70}, {978, 603}, {55, 803}, {89, 160}, {490,
598}, {888, 100}, {475, 973}, {880, 544}, {231, 894}, {546, 77}, {612,
810}, {410, 882}, {964, 539}, {816, 920}, {809, 528}, {848, 472}, {202,
291}, {724, 5}, {594, 131}, {385, 738}, {95, 277}, {432, 829}, {218, 434},
{21, 127}, {926, 930}, {522, 650}, {563, 734}, {940, 927}, {733, 830},
{494, 847}, {193, 290}, {492, 456}, {961, 47}, {876, 891}, {711, 827},
{715, 474}, {489, 253}, {678, 289}, {398, 385}, {433, 146}, {173, 189},
{985, 296}, {401, 357}, {592, 386}, {725, 243}, {308, 332}, {244, 637},
{253, 938}, {852, 905}, {366, 712}, {560, 854}, {669, 270}, {666, 915},
{362, 933}, {344, 832}, {255, 526}, {735, 438}, {400, 804}, {144, 230},
{304, 338}, {287, 577}, {842, 8}, {327, 383}, {700, 41}, {499, 713}, {343,
629}, {969, 654}, {24, 916}, {686, 276}, {525, 722}, {769, 302}, {240, 56},
{828, 236}, {554, 486}, {727, 969}, {775, 356}, {411, 369}, {42, 943}, {70,
429}, {824, 292}, {747, 577}, {359, 193}, {869, 301}, {390, 377}, {763,
507}, {489, 526}, {63, 869}, {504, 647}, {525, 315}, {330, 65}, {818, 970},
{976, 690}, {593, 324}, {242, 378}, {734, 271}, {120, 111}, {891, 898},
{70, 675}, {929, 823}, {742, 330}, {347, 904}, {142, 496}, {353, 505},
{448, 352}, {325, 794}, {54, 485}, {543, 70}, {763, 423}, {142, 846}, {112,
7}, {652, 82}, {999, 939}, {402, 293}, {378, 300}, {717, 731}, {412, 885},
{827, 595}, {179, 823}, {389, 424}, {353, 533}, {229, 511}, {889, 743},
{235, 394}, {717, 22}, {121, 962}, {31, 991}, {843, 687}, {904, 89}, {695,
705}, {624, 573}, {869, 643}, {887, 495}, {340, 827}, {833, 219}, {746,
804}, {547, 350}, {127, 206}, {755, 827}, {108, 539}, {586, 321}, {451,
251}, {860, 409}, {505, 953}, {713, 909}, {177, 226}, {15, 708}, {425,
339}, {80, 63}, {181, 26}, {419, 139}, {298, 680}, {805, 607}, {259, 545},
{451, 440}, {880, 225}, {255, 259}, {337, 637}, {974, 363}, {849, 850},
{905, 206}, {868, 820}, {972, 972}, {736, 724}, {305, 420}, {63, 848},
{947, 836}, {39, 947}, {355, 636}, {418, 13}, {816, 641}, {845, 374}, {359,
921}, {322, 65}, {165, 728}, {997, 813}, {77, 344}, {340, 390}, {264, 367},
{261, 712}, {953, 838}, {204, 743}, {48, 398}, {801, 61}, {186, 700}, {854,
109}, {624, 172}, {304, 915}, {426, 711}, {45, 117}, {321, 549}, {387,
555}, {206, 970}, {791, 317}, {786, 20}, {343, 594}, {361, 382}, {278,
277}, {331, 225}, {510, 807}, {441, 493}, {396, 271}, {797, 678}, {254,
123}, {539, 172}, {380, 267}, {420, 211}, {96, 247}, {407, 644}, {869,
814}, {202, 338}, {327, 759}, {734, 713}, {18, 699}, {827, 103}, {953,
551}, {206, 734}, {499, 98}, {66, 784}, {346, 444}, {824, 654}, {3, 224},
{519, 231}, {319, 627}, {816, 292}, {81, 9}, {926, 899}, {27, 659}, {432,
183}, {170, 709}, {522, 394}, {165, 264}, {469, 54}, {838, 705}, {101,
415}, {713, 54}, {828, 650}, {480, 333}, {899, 162}, {830, 709}, {93, 789},
{192, 173}, {720, 943}, {921, 758}, {100, 616}, {611, 62}, {168, 702},
{776, 468}, {417, 79}, {420, 73}, {415, 149}, {383, 193}, {258, 597}, {871,
677}, {327, 545}, {693, 93}, {714, 7}, {313, 135}, {788, 457}, {976, 961},
{680, 113}, {422, 998}, {162, 301}, {269, 440}, {834, 25}, {559, 853},
{787, 947}, {919, 930}, {910, 932}, {970, 417}, {846, 238}, {252, 741},
{119, 401}, {136, 438}, {829, 432}, {614, 245}, {890, 7}, {303, 367}, {498,
31}, {363, 384}, {805, 632}, {476, 821}, {940, 345}, {526, 932}, {966,
643}, {572, 542}, {504, 255}, {841, 653}, {63, 91}, {97, 440}, {885, 550},
{156, 851}, {190, 241}, {105, 859}, {264, 18}, {704, 965}, {598, 654},
{922, 197}, {18, 543}, {677, 871}, {168, 514}, {334, 157}, {294, 553},
{466, 973}, {792, 673}, {541, 331}, {307, 943}, {640, 551}, {947, 250},
{390, 780}, {343, 379}, {80, 340}, {838, 145}, {634, 45}, {410, 2}, {934,
338}, {621, 206}, {606, 977}, {735, 258}, {373, 274}, {631, 574}, {120,
947}, {882, 725}, {139, 294}, {694, 450}, {476, 201}, {815, 305}, {234,
563}, {305, 214}, {498, 39}, {753, 93}, {863, 81}, {202, 617}, {341, 719},
{118, 153}, {586, 342}, {624, 806}, {498, 730}, {64, 211}, {858, 569},
{541, 202}, {204, 259}, {517, 187}, {3, 682}, {36, 760}, {300, 287}, {980,
873}, {260, 430}, {427, 411}, {677, 520}, {119, 515}, {18, 823}, {530, 39},
{728, 185}, {537, 856}, {190, 883}, {409, 157}, {442, 271}, {347, 185},
{884, 749}, {757, 55}, {394, 98}, {662, 829}, {32, 751}, {685, 491}, {937,
571}, {624, 613}, {3, 417}, {90, 932}, {48, 377}, {541, 231}, {498, 940},
{573, 755}, {157, 40}, {888, 205}, {161, 489}, {344, 601}, {300, 543},
{319, 378}, {257, 918}, {536, 295}, {738, 305}, {970, 797}, {609, 698},
{90, 668}, {114, 527}, {116, 267}, {429, 953}, {273, 401}, {76, 772}, {806,
158}, {411, 627}, {271, 128}, {177, 72}, {995, 652}, {574, 35}, {250, 284},
{283, 339}, {154, 304}, {602, 904}, {465, 102}, {709, 747}, {952, 735},
{12, 418}, {473, 24}, {24, 880}, {38, 195}, {34, 797}, {647, 687}, {34,
367}, {165, 62}, {454, 192}, {949, 492}, {671, 677}, {868, 896}, {333,
965}, {846, 833}, {486, 905}, {123, 273}, {495, 697}, {319, 687}, {20,
827}, {863, 991}, {530, 940}, {934, 56}, {2, 922}, {423, 716}, {863, 560},
{447, 208}, {300, 597}, {941, 567}, {652, 665}, {668, 666}, {962, 732},
{221, 61}, {108, 983}, {359, 374}, {589, 882}, {545, 460}, {728, 281},
{101, 286}, {913, 474}, {819, 438}, {189, 863}, {377, 662}, {715, 322},
{851, 766}, {957, 400}, {948, 312}, {444, 219}, {708, 763}, {19, 939},
{390, 433}, {629, 689}, {55, 92}, {854, 656}, {67, 592}, {104, 334}, {578,
863}, {961, 905}, {607, 412}, {177, 53}, {799, 76}, {891, 446}, {343, 78},
{112, 79}, {872, 242}, {604, 137}, {606, 267}, {158, 640}, {559, 979},
{908, 154}, {532, 630}, {519, 234}, {647, 247}, {690, 376}, {193, 268},
{617, 89}, {561, 501}, {719, 455}, {820, 890}, {568, 977}, {363, 416},
{234, 833}, {851, 107}, {213, 609}, {140, 436}, {229, 40}, {438, 262}, {77,
404}, {686, 9}, {42, 545}, {398, 433}, {759, 105}, {13, 808}, {727, 495},
{918, 189}, {879, 817}, {45, 747}, {335, 886}, {266, 985}, {708, 643},
{200, 613}, {855, 834}, {980, 575}, {756, 71}, {609, 504}, {711, 333},
{798, 973}, {316, 946}, {444, 449}, {213, 929}, {860, 579}, {683, 38}, {8,
863}, {992, 618}, {407, 715}, {791, 526}, {848, 85}, {30, 690}, {468, 208},
{238, 404}, {989, 480}, {662, 156}, {670, 160}, {691, 172}, {16, 903},
{620, 93}, {856, 96}, {308, 571}, {479, 881}, {44, 903}, {621, 540}, {9,
168}, {481, 405}, {551, 995}, {172, 260}, {369, 659}, {110, 855}, {880,
298}, {687, 388}, {95, 828}, {960, 512}, {968, 6}, {878, 909}, {138, 124},
{751, 408}, {252, 243}, {683, 119}, {573, 282}, {768, 782}, {415, 691},
{272, 643}, {108, 966}, {657, 186}, {486, 665}, {889, 927}, {565, 826},
{901, 858}, {99, 999}, {748, 415}, {571, 472}, {910, 484}, {905, 735},
{894, 229}, {381, 908}, {944, 320}, {815, 85}, {177, 915}, {669, 415},
{686, 425}, {19, 242}, {985, 845}, {213, 277}, {955, 349}, {940, 804},
{954, 198}, {403, 329}, {87, 855}, {239, 563}, {152, 898}, {544, 643},
{760, 95}, {780, 501}, {470, 475}, {301, 646}, {298, 5}, {795, 899}, {82,
558}, {778, 360}, {209, 706}, {589, 301}, {719, 798}, {268, 205}, {327,
460}, {470, 22}, {660, 372}, {96, 497}, {485, 760}, {168, 821}, {215, 332},
{276, 112}, {332, 804}, {808, 747}, {673, 35}, {605, 230}, {987, 466},
{179, 383}, {705, 165}, {356, 404}, {943, 208}, {14, 50}, {776, 346}, {789,
358}, {751, 233}, {303, 306}, {654, 843}, {841, 547}, {263, 35}, {218,
227}, {462, 727}, {52, 64}, {220, 173}, {675, 635}, {856, 409}, {495, 696},
{664, 132}, {388, 849}, {766, 515}, {781, 228}, {145, 633}, {405, 645},
{426, 954}, {793, 318}, {46, 30}, {848, 998}, {907, 612}, {163, 173}, {670,
712}, {356, 239}, {966, 345}, {341, 388}, {435, 237}, {459, 470}, {466,
310}, {380, 128}, {174, 263}, {28, 118}, {119, 782}, {531, 8}, {930, 160},
{604, 165}, {131, 773}, {949, 844}, {753, 316}, {740, 917}, {78, 608},
{917, 51}, {923, 824}, {381, 895}, {61, 109}, {959, 224}, {357, 393}, {756,
289}, {826, 231}, {23, 535}, {416, 756}, {812, 411}, {1, 12}, {340, 746},
{472, 109}, {467, 595}, {218, 179}, {582, 756}, {801, 138}, {698, 895},
{43, 359}, {999, 378}, {624, 595}, {37, 23}, {454, 226}, {70, 213}, {676,
673}, {654, 62}, {249, 809}, {150, 776}, {192, 442}, {875, 325}, {706,
628}, {212, 638}, {597, 149}, {205, 604}, {951, 189}, {641, 944}, {915,
487}, {944, 532}, {460, 48}, {95, 482}, {735, 61}, {136, 970}, {788, 733},
{533, 485}, {533, 660}, {758, 626}, {777, 313}, {702, 720}, {709, 926},
{777, 297}, {332, 698}, {552, 27}, {465, 725}, {330, 473}, {938, 20}, {276,
605}, {454, 844}, {950, 805}, {276, 408}, {391, 773}, {297, 949}, {64, 38},
{177, 236}, {76, 498}, {218, 521}, {582, 428}, {205, 175}, {987, 756},
{247, 115}, {815, 970}, {860, 775}, {319, 15}, {860, 36}, {326, 228}, {966,
293}, {257, 159}, {935, 552}, {34, 735}, {39, 165}, {878, 215}, {405, 352},
{72, 298}, {927, 771}, {896, 66}, {116, 677}, {36, 268}, {546, 11}, {742,
766}, {42, 783}, {774, 864}, {245, 4}, {932, 149}, {77, 509}, {714, 65},
{839, 333}, {204, 656}, {345, 375}, {855, 807}, {466, 109}, {727, 880},
{948, 413}, {5, 541}, {355, 443}, {583, 629}, {350, 688}, {739, 416}, {329,
182}, {185, 140}, {713, 911}, {950, 346}, {927, 204}, {375, 753}, {974,
735}, {28, 783}, {706, 207}, {0, 21}, {842, 758}, {743, 924}, {966, 312},
{329, 675}, {291, 490}, {329, 493}, {523, 862}, {916, 834}, {860, 424},
{861, 46}, {617, 363}, {844, 174}, {309, 106}, {45, 899}, {353, 567}, {783,
689}, {681, 155}, {524, 933}, {980, 142}, {69, 794}, {417, 89}, {562, 922},
{741, 86}, {74, 996}, {813, 989}, {694, 73}, {680, 415}, {772, 797}, {982,
101}, {283, 936}, {825, 226}, {945, 394}, {740, 599}, {68, 519}, {979,
192}, {138, 4}, {201, 791}, {595, 210}, {215, 215}, {802, 488}, {539, 277},
{919, 844}, {746, 495}, {604, 1}, {951, 456}, {51, 346}, {214, 108}, {587,
565}, {464, 939}, {109, 945}, {691, 274}, {878, 197}, {311, 534}, {458,
992}, {737, 696}, {853, 295}, {156, 139}, {285, 518}, {92, 169}, {590,
142}, {263, 792}, {109, 656}, {406, 132}, {610, 734}, {359, 367}, {206,
953}, {883, 324}, {669, 123}, {878, 598}, {569, 32}, {422, 527}, {957,
964}, {700, 522}, {333, 719}, {647, 832}, {269, 457}, {703, 110}, {512,
238}, {233, 121}, {710, 179}, {802, 93}, {715, 825}, {321, 307}, {866,
980}, {231, 586}, {845, 456}, {26, 265}, {656, 883}, {221, 951}, {131, 80},
{629, 876}, {736, 293}, {171, 526}, {121, 189}, {269, 962}, {709, 939},
{800, 320}, {874, 235}, {728, 670}, {821, 325}, {149, 445}, {17, 593},
{573, 443}, {879, 321}, {718, 148}, {282, 455}, {420, 144}, {449, 303},
{404, 53}, {958, 594}, {855, 155}, {33, 537}, {179, 325}, {907, 621}, {26,
951}, {722, 289}, {213, 846}, {141, 106}, {530, 683}, {905, 934}, {425,
686}, {486, 256}, {47, 82}, {133, 45}, {526, 690}, {733, 856}, {144, 172},
{69, 853}, {658, 302}, {64, 165}, {957, 613}, {29, 136}, {464, 346}, {114,
87}, {832, 654}, {631, 900}, {96, 461}, {657, 458}, {863, 372}, {217, 614},
{352, 705}, {791, 378}, {617, 550}, {222, 578}, {86, 907}, {163, 593},
{410, 307}, {603, 403}, {335, 892}, {20, 926}, {400, 745}, {747, 190},
{443, 698}, {705, 735}, {169, 30}, {921, 106}, {167, 498}, {11, 339}, {89,
578}, {470, 594}, {325, 50}, {127, 952}, {767, 463}, {887, 49}, {193, 249},
{69, 487}, {723, 280}, {294, 744}, {242, 384}, {685, 92}, {975, 970}, {824,
253}, {592, 419}, {278, 481}, {361, 162}, {439, 17}, {881, 221}, {4, 615},
{399, 211}, {546, 45}, {834, 438}, {553, 879}, {603, 895}, {412, 366}, {63,
697}, {16, 246}, {808, 2}, {73, 225}, {288, 607}, {475, 616}, {428, 999},
{560, 595}, {421, 404}, {563, 899}, {126, 138}, {388, 419}, {47, 376},
{305, 1}, {420, 381}, {501, 447}, {378, 720}, {469, 301}, {584, 853}, {659,
498}, {849, 517}, {970, 851}, {840, 212}, {612, 508}, {38, 471}, {98, 504},
{143, 368}, {846, 492}, {760, 788}, {720, 353}, {115, 858}, {389, 911},
{142, 719}, {960, 273}, {97, 714}, {306, 744}, {336, 321}, {684, 493},
{951, 464}, {985, 894}, {627, 860}, {550, 559}, {503, 840}, {473, 170},
{322, 672}, {521, 717}, {329, 566}, {703, 582}, {934, 969}, {313, 635},
{698, 984}, {128, 880}, {658, 154}, {524, 145}, {9, 315}, {71, 425}, {565,
104}, {817, 84}, {429, 976}, {601, 279}, {695, 146}, {210, 144}, {740,
609}, {872, 201}, {163, 52}, {857, 27}, {699, 499}, {921, 545}, {730, 762},
{850, 326}, {609, 673}, {699, 453}, {910, 238}, {592, 215}, {573, 850},
{749, 217}, {449, 592}, {468, 331}, {476, 543}, {16, 800}, {361, 250},
{995, 363}, {288, 858}, {971, 118}, {541, 583}, {561, 587}, {832, 293},
{660, 60}, {247, 685}, {799, 279}, {169, 913}, {115, 746}, {91, 341}, {153,
758}, {985, 628}, {116, 170}, {791, 712}, {449, 731}, {4, 719}, {975, 88},
{292, 114}, {670, 607}, {4, 178}, {8, 389}, {492, 51}, {183, 606}, {314,
888}, {571, 887}, {182, 275}, {572, 352}, {903, 459}, {131, 558}, {681,
288}, {40, 333}, {587, 267}, {483, 764}, {966, 348}, {676, 279}, {141,
409}, {904, 760}, {740, 406}, {474, 565}, {932, 428}, {40, 192}, {539,
232}, {613, 528}, {207, 63}, {321, 714}, {872, 570}, {862, 809}, {882,
348}, {594, 603}, {756, 279}, {531, 767}, {993, 556}, {666, 276}, {961,
176}, {573, 800}, {417, 146}, {863, 327}, {627, 118}, {692, 250}, {272,
244}, {587, 159}, {22, 704}, {263, 515}, {492, 19}, {728, 979}, {257, 917},
{383, 409}, {58, 423}, {480, 417}, {399, 716}, {374, 633}, {408, 265},
{762, 749}, {695, 629}, {893, 272}, {285, 719}, {673, 456}, {690, 491},
{243, 595}, {425, 955}, {558, 459}, {485, 562}, {47, 996}, {902, 486},
{581, 716}, {525, 812}, {519, 945}, {923, 918}, {607, 572}, {882, 719},
{544, 313}, {136, 36}, {977, 567}, {23, 244}, {777, 198}, {515, 590}, {349,
90}, {858, 183}, {271, 996}, {116, 821}, {267, 829}, {576, 681}, {718,
619}, {614, 393}, {571, 478}, {647, 840}, {843, 691}, {387, 201}, {330,
391}, {667, 494}, {504, 437}, {111, 560}, {800, 103}, {931, 618}, {322,
595}, {634, 848}, {96, 443}, {804, 14}, {647, 636}, {496, 521}, {529, 633},
{556, 117}, {600, 162}, {211, 432}, {550, 909}, {890, 45}, {725, 61}, {147,
626}, {482, 894}, {755, 159}, {55, 731}, {352, 488}, {934, 163}, {93, 653},
{524, 36}, {607, 528}, {341, 126}, {425, 87}, {354, 490}, {22, 72}, {869,
869}, {671, 203}, {181, 372}, {105, 40}, {634, 342}, {229, 923}, {271,
472}, {325, 837}, {929, 218}, {968, 410}, {144, 628}, {716, 344}, {983,
457}, {237, 209}, {400, 562}, {271, 227}, {134, 461}, {587, 903}, {658,
519}, {172, 354}, {530, 739}, {244, 175}, {883, 940}, {786, 638}, {725,
141}, {316, 830}, {584, 514}, {729, 900}, {481, 737}, {800, 228}, {478, 8},
{36, 395}, {684, 178}, {369, 397}, {824, 109}, {792, 796}, {756, 679},
{699, 241}, {227, 789}, {510, 521}, {665, 375}, {107, 595}, {565, 386},
{687, 129}, {498, 585}, {897, 718}, {275, 767}, {538, 469}, {849, 208},
{15, 349}, {518, 750}, {416, 158}, {577, 390}, {751, 420}, {892, 233},
{793, 895}, {870, 691}, {339, 125}, {41, 403}, {784, 7}, {426, 181}, {197,
430}, {71, 474}, {950, 597}, {183, 147}, {186, 939}, {679, 571}, {209,
878}, {836, 395}, {391, 472}, {934, 326}, {536, 151}, {238, 925}, {38,
763}, {425, 185}, {308, 254}, {110, 47}, {599, 993}, {236, 918}, {64, 337},
{41, 57}, {676, 439}, {378, 388}, {845, 335}, {130, 115}, {662, 594}, {281,
557}, {867, 935}, {236, 982}, {896, 905}, {952, 302}, {440, 186}, {46,
229}, {301, 727}, {634, 140}, {85, 411}, {256, 571}, {16, 616}, {729, 321},
{316, 102}, {756, 885}, {482, 617}, {98, 90}, {550, 914}, {651, 19}, {174,
642}, {484, 245}, {949, 551}, {130, 581}, {745, 75}, {799, 498}, {375, 30},
{30, 333}, {195, 199}, {80, 717}, {133, 852}, {464, 906}, {137, 642}, {108,
772}, {833, 352}, {975, 236}, {799, 557}, {571, 106}, {237, 379}, {698,
712}, {618, 735}, {352, 682}, {754, 799}, {981, 502}, {976, 721}, {216,
281}, {470, 956}, {322, 777}, {387, 286}, {682, 601}, {351, 208}, {662,
912}, {812, 226}, {806, 450}, {560, 469}, {94, 346}, {350, 347}, {625,
116}, {21, 708}, {246, 770}, {17, 194}, {696, 357}, {397, 824}, {337, 647},
{347, 913}, {989, 966}, {865, 180}, {669, 562}, {996, 627}, {455, 299},
{672, 664}, {127, 377}, {646, 630}, {688, 232}, {584, 944}, {359, 678},
{669, 61}, {628, 693}, {407, 293}, {206, 220}, {921, 248}, {750, 96}, {635,
432}, {197, 304}, {692, 814}, {90, 506}, {407, 172}, {999, 392}, {851,
698}, {479, 678}, {559, 484}, {837, 77}, {625, 13}, {837, 672}, {990, 558},
{176, 124}, {366, 101}, {624, 558}, {69, 197}, {715, 502}, {186, 413},
{614, 999}, {994, 827}, {964, 576}, {520, 539}, {599, 5}, {501, 329}, {954,
376}, {276, 766}, {586, 487}, {765, 221}, {381, 549}, {257, 476}, {267,
772}, {44, 362}, {961, 300}, {811, 52}, {264, 264}, {365, 994}, {776, 246},
{943, 689}, {53, 545}, {93, 179}, {586, 443}, {861, 552}, {677, 338}, {448,
496}, {740, 410}, {488, 537}, {588, 939}, {988, 592}, {448, 853}, {939,
535}, {481, 302}, {241, 570}, {257, 231}, {706, 565}, {161, 725}, {509,
477}, {555, 367}, {892, 476}, {287, 492}, {756, 49}, {305, 257}, {976,
210}, {630, 406}, {792, 899}, {566, 152}, {801, 657}, {707, 759}, {49,
246}, {812, 444}, {800, 615}, {484, 520}, {912, 857}, {26, 649}, {699,
806}, {219, 916}, {300, 9}, {972, 176}, {447, 722}, {622, 791}, {806, 7},
{824, 747}, {572, 233}, {741, 433}, {201, 402}, {262, 236}, {685, 390},
{246, 64}, {190, 960}, {199, 936}, {984, 415}, {671, 121}, {739, 895},
{239, 647}, {439, 129}, {6, 796}, {623, 682}, {429, 487}, {348, 180}, {299,
899}, {834, 206}, {657, 78}, {155, 359}, {9, 884}, {660, 712}, {622, 243},
{861, 605}, {570, 666}, {202, 614}, {933, 742}, {946, 580}, {797, 961},
{376, 382}, {159, 153}, {925, 179}, {639, 942}, {233, 640}, {895, 229},
{37, 552}, {850, 532}, {133, 500}, {740, 928}, {418, 742}, {994, 330},
{694, 468}, {9, 545}, {171, 926}, {369, 674}, {333, 905}, {675, 27}, {479,
266}, {122, 397}, {724, 366}, {363, 633}, {974, 268}, {243, 38}, {519,
977}, {183, 256}, {80, 356}, {688, 363}, {964, 704}, {39, 806}, {102, 218},
{865, 619}, {406, 385}, {354, 605}, {694, 495}, {159, 269}, {425, 290},
{858, 232}, {338, 45}, {420, 337}, {404, 153}, {471, 485}, {639, 532},
{628, 607}, {980, 680}, {826, 492}, {382, 321}, {33, 366}, {709, 250},
{644, 122}, {763, 175}, {86, 126}, {606, 304}, {689, 490}, {791, 427},
{732, 659}, {443, 40}, {773, 967}, {223, 400}, {473, 851}, {294, 983}, {76,
705}, {310, 932}, {908, 862}, {451, 940}, {660, 670}, {250, 128}, {315,
347}, {383, 576}, {121, 152}, {373, 334}, {963, 908}, {912, 936}, {974,
563}, {989, 207}, {76, 699}, {239, 737}, {921, 325}, {819, 508}, {313,
871}, {640, 904}, {679, 409}, {272, 429}, {793, 494}, {281, 143}, {446,
929}, {961, 471}, {688, 492}, {519, 461}, {492, 569}, {258, 430}, {46,
387}, {265, 162}, {746, 960}, {729, 795}, {304, 753}, {691, 833}, {941,
109}, {97, 570}, {26, 652}, {842, 661}, {510, 778}, {883, 982}, {711, 605},
{209, 160}, {182, 364}, {149, 82}, {245, 435}, {247, 818}, {499, 301},
{820, 669}, {381, 89}, {899, 165}, {398, 969}, {22, 147}, {0, 1}, {0, 3},
{0, 4}, {0, 7}, {0, 8}, {0, 10}, {0, 15}, {0, 16}, {0, 18}, {0, 31}, {0,
32}, {0, 34}, {0, 35}, {0, 38}, {0, 41}, {0, 46}, {0, 57}, {0, 62}, {0,
63}, {0, 65}, {0, 69}, {0, 72}, {0, 77}, {0, 85}, {0, 88}, {0, 94}, {0,
96}, {0, 97}, {0, 108}, {0, 125}, {0, 126}, {0, 128}, {0, 132}, {0, 140},
{0, 147}, {0, 156}, {0, 157}, {0, 160}, {0, 163}, {0, 166}, {0, 187}, {0,
191}, {0, 195}, {0, 203}, {0, 205}, {0, 213}, {0, 218}, {0, 221}, {0, 250},
{0, 253}, {0, 257}, {0, 260}, {0, 265}, {0, 266}, {0, 268}, {0, 269}, {0,
281}, {0, 285}, {0, 306}, {0, 312}, {0, 313}, {0, 316}, {0, 327}, {0, 343},
{0, 378}, {0, 382}, {0, 401}, {0, 406}, {0, 444}, {0, 471}, {0, 483}, {0,
484}, {0, 500}, {0, 501}, {0, 503}, {0, 504}, {0, 507}, {0, 515}, {0, 518},
{0, 522}, {0, 532}, {0, 542}, {0, 562}, {0, 565}, {0, 569}, {0, 612}, {0,
625}, {0, 626}, {0, 628}, {0, 632}, {0, 650}, {0, 697}, {0, 750}, {0, 751},
{0, 754}, {0, 757}, {0, 760}, {0, 781}, {0, 784}, {0, 785}, {0, 797}, {0,
813}, {0, 837}, {0, 898}, {1, 0}, {1, 3}, {1, 4}, {1, 7}, {1, 15}, {1, 18},
{1, 19}, {1, 25}, {1, 31}, {1, 34}, {1, 35}, {1, 46}, {1, 62}, {1, 63}, {1,
65}, {1, 69}, {1, 80}, {1, 93}, {1, 125}, {1, 132}, {1, 135}, {1, 144}, {1,
156}, {1, 171}, {1, 194}, {1, 233}, {1, 250}, {1, 254}, {1, 266}, {1, 281},
{1, 285}, {1, 313}, {1, 327}, {1, 344}, {1, 409}, {1, 437}, {1, 452}, {1,
475}, {1, 500}, {1, 515}, {1, 531}, {1, 565}, {1, 593}, {1, 600}, {1, 628},
{1, 632}, {3, 0}, {3, 1}, {3, 7}, {3, 15}, {3, 26}, {3, 31}, {3, 32}, {3,
34}, {3, 46}, {3, 62}, {3, 63}, {3, 65}, {3, 69}, {3, 111}, {3, 125}, {3,
132}, {3, 140}, {3, 141}, {3, 143}, {3, 156}, {3, 187}, {3, 250}, {3, 269},
{3, 281}, {3, 312}, {3, 327}, {3, 328}, {3, 346}, {3, 437}, {3, 500}, {3,
501}, {3, 508}, {3, 515}, {3, 519}, {3, 547}, {3, 562}, {3, 594}, {3, 663},
{3, 698}, {3, 750}, {3, 765}, {3, 885}, {4, 0}, {4, 7}, {4, 16}, {4, 23},
{4, 26}, {4, 31}, {4, 57}, {4, 125}, {4, 150}, {4, 229}, {4, 236}, {4,
258}, {4, 625}, {4, 671}, {4, 688}, {4, 843}, {7, 0}, {7, 1}, {7, 3}, {7,
15}, {7, 16}, {7, 18}, {7, 22}, {7, 31}, {7, 62}, {7, 69}, {7, 93}, {7,
125}, {7, 132}, {7, 135}, {7, 140}, {7, 159}, {7, 187}, {7, 202}, {7, 236},
{7, 257}, {7, 265}, {7, 273}, {7, 284}, {7, 313}, {7, 315}, {7, 382}, {7,
383}, {7, 390}, {7, 452}, {7, 503}, {7, 515}, {7, 518}, {7, 531}, {7, 538},
{7, 549}, {7, 562}, {7, 565}, {7, 628}, {7, 750}, {7, 843}, {7, 876}, {8,
3}, {8, 4}, {8, 7}, {8, 15}, {8, 22}, {8, 31}, {8, 47}, {8, 49}, {8, 135},
{8, 159}, {8, 228}, {8, 250}, {8, 437}, {8, 508}, {8, 566}, {10, 0}, {10,
1}, {10, 15}, {10, 16}, {10, 31}, {10, 41}, {10, 62}, {10, 125}, {10, 140},
{10, 205}, {10, 250}, {10, 375}, {10, 562}, {10, 656}, {10, 882}, {11, 0},
{11, 62}, {11, 265}, {11, 281}, {11, 625}, {15, 0}, {15, 1}, {15, 4}, {15,
7}, {15, 10}, {15, 16}, {15, 18}, {15, 31}, {15, 38}, {15, 46}, {15, 54},
{15, 62}, {15, 63}, {15, 69}, {15, 73}, {15, 93}, {15, 94}, {15, 109}, {15,
125}, {15, 175}, {15, 190}, {15, 225}, {15, 254}, {15, 281}, {15, 284},
{15, 316}, {15, 346}, {15, 406}, {15, 422}, {15, 500}, {15, 501}, {15,
510}, {15, 515}, {15, 523}, {15, 562}, {15, 625}, {15, 702}, {15, 753},
{15, 781}, {15, 791}, {16, 0}, {16, 1}, {16, 3}, {16, 10}, {16, 18}, {16,
22}, {16, 62}, {16, 65}, {16, 140}, {16, 167}, {16, 282}, {16, 330}, {16,
500}, {16, 503}, {16, 516}, {16, 562}, {16, 570}, {16, 641}, {16, 750},
{16, 784}, {18, 1}, {18, 7}, {18, 22}, {18, 65}, {18, 132}, {18, 147}, {18,
171}, {18, 187}, {18, 222}, {18, 251}, {18, 253}, {18, 268}, {18, 312},
{18, 413}, {18, 422}, {18, 515}, {18, 516}, {18, 633}, {18, 758}, {19, 0},
{19, 3}, {19, 4}, {19, 46}, {19, 273}, {19, 289}, {19, 750}, {22, 0}, {22,
31}, {22, 34}, {22, 38}, {22, 46}, {22, 69}, {22, 70}, {22, 187}, {22,
222}, {22, 250}, {22, 291}, {22, 312}, {22, 313}, {22, 359}, {22, 382},
{22, 390}, {22, 437}, {22, 626}, {22, 641}, {23, 0}, {23, 41}, {23, 78},
{23, 100}, {23, 281}, {23, 375}, {25, 0}, {25, 62}, {25, 140}, {25, 187},
{25, 531}, {25, 844}, {26, 108}, {26, 394}, {31, 0}, {31, 1}, {31, 3}, {31,
7}, {31, 15}, {31, 18}, {31, 47}, {31, 53}, {31, 65}, {31, 93}, {31, 108},
{31, 112}, {31, 126}, {31, 140}, {31, 156}, {31, 157}, {31, 163}, {31,
187}, {31, 202}, {31, 253}, {31, 265}, {31, 268}, {31, 312}, {31, 375},
{31, 393}, {31, 468}, {31, 500}, {31, 503}, {31, 504}, {31, 507}, {31,
510}, {31, 516}, {31, 538}, {31, 569}, {31, 687}, {31, 750}, {31, 812},
{31, 876}, {32, 0}, {32, 3}, {32, 4}, {32, 18}, {32, 25}, {32, 26}, {32,
46}, {32, 62}, {32, 140}, {32, 257}, {32, 272}, {32, 327}, {32, 382}, {32,
500}, {32, 587}, {34, 0}, {34, 15}, {34, 16}, {34, 38}, {34, 46}, {34, 63},
{34, 115}, {34, 126}, {34, 141}, {34, 265}, {34, 501}, {34, 508}, {34,
538}, {34, 597}, {34, 750}, {35, 0}, {35, 3}, {35, 31}, {35, 34}, {35, 62},
{35, 69}, {35, 80}, {35, 171}, {35, 508}, {38, 0}, {38, 7}, {38, 16}, {38,
18}, {38, 25}, {38, 63}, {38, 66}, {38, 70}, {38, 96}, {38, 125}, {38,
251}, {38, 265}, {38, 291}, {38, 313}, {38, 315}, {38, 316}, {38, 376},
{38, 569}, {38, 625}, {38, 750}, {38, 757}, {38, 785}, {38, 875}, {39, 34},
{39, 69}, {39, 125}, {39, 132}, {39, 266}, {39, 319}, {41, 50}, {41, 250},
{41, 750}, {41, 765}, {42, 3}, {42, 312}, {46, 0}, {46, 1}, {46, 3}, {46,
4}, {46, 7}, {46, 10}, {46, 15}, {46, 16}, {46, 25}, {46, 77}, {46, 163},
{46, 265}, {46, 500}, {46, 501}, {46, 515}, {47, 101}, {47, 143}, {47,
265}, {49, 1}, {49, 7}, {49, 125}, {49, 202}, {49, 257}, {49, 656}, {49,
907}, {50, 22}, {53, 11}, {53, 228}, {53, 688}, {54, 62}, {54, 554}, {56,
0}, {56, 1}, {56, 10}, {56, 31}, {56, 128}, {62, 0}, {62, 1}, {62, 3}, {62,
4}, {62, 7}, {62, 10}, {62, 15}, {62, 16}, {62, 18}, {62, 25}, {62, 31},
{62, 32}, {62, 35}, {62, 38}, {62, 46}, {62, 47}, {62, 65}, {62, 66}, {62,
69}, {62, 96}, {62, 108}, {62, 125}, {62, 126}, {62, 135}, {62, 140}, {62,
144}, {62, 147}, {62, 159}, {62, 187}, {62, 188}, {62, 250}, {62, 251},
{62, 253}, {62, 257}, {62, 265}, {62, 288}, {62, 312}, {62, 319}, {62,
353}, {62, 375}, {62, 376}, {62, 500}, {62, 504}, {62, 508}, {62, 510},
{62, 525}, {62, 534}, {62, 538}, {62, 569}, {62, 625}, {62, 635}, {62,
750}, {62, 812}, {62, 850}, {62, 851}, {63, 0}, {63, 1}, {63, 8}, {63, 46},
{63, 65}, {63, 140}, {63, 171}, {63, 202}, {63, 250}, {63, 281}, {63, 284},
{63, 503}, {63, 515}, {63, 518}, {63, 538}, {63, 562}, {63, 593}, {63,
734}, {65, 0}, {65, 3}, {65, 4}, {65, 15}, {65, 16}, {65, 38}, {65, 87},
{65, 112}, {65, 125}, {65, 126}, {65, 132}, {65, 133}, {65, 140}, {65,
174}, {65, 266}, {65, 312}, {65, 375}, {65, 437}, {65, 503}, {65, 508},
{65, 562}, {65, 626}, {66, 0}, {66, 46}, {66, 93}, {66, 257}, {66, 500},
{66, 772}, {69, 1}, {69, 7}, {69, 11}, {69, 18}, {69, 62}, {69, 132}, {69,
234}, {69, 257}, {69, 281}, {69, 296}, {69, 504}, {69, 532}, {69, 562},
{69, 572}, {69, 694}, {69, 750}, {69, 757}, {70, 0}, {70, 15}, {70, 18},
{70, 63}, {70, 157}, {70, 171}, {70, 250}, {70, 757}, {72, 32}, {72, 190},
{72, 218}, {72, 291}, {72, 659}, {73, 0}, {73, 187}, {73, 250}, {73, 281},
{73, 328}, {73, 500}, {77, 1}, {77, 3}, {77, 31}, {77, 38}, {77, 78}, {77,
129}, {77, 171}, {77, 198}, {77, 250}, {77, 281}, {77, 508}, {77, 510},
{77, 538}, {77, 563}, {77, 750}, {77, 754}, {77, 765}, {77, 768}, {77,
937}, {78, 0}, {78, 1}, {78, 31}, {78, 218}, {78, 269}, {78, 376}, {80, 0},
{80, 8}, {80, 10}, {80, 31}, {80, 69}, {80, 250}, {80, 269}, {80, 285},
{80, 500}, {80, 547}, {81, 3}, {81, 31}, {81, 515}, {81, 531}, {84, 10},
{84, 15}, {84, 132}, {84, 190}, {84, 250}, {84, 507}, {84, 532}, {84, 534},
{84, 878}, {85, 126}, {85, 312}, {87, 140}, {93, 0}, {93, 3}, {93, 7}, {93,
15}, {93, 18}, {93, 46}, {93, 53}, {93, 63}, {93, 132}, {93, 228}, {93,
250}, {93, 261}, {93, 379}, {93, 383}, {93, 444}, {93, 507}, {93, 515},
{93, 534}, {93, 562}, {94, 3}, {94, 34}, {94, 62}, {94, 500}, {94, 515},
{94, 632}, {96, 38}, {96, 46}, {96, 53}, {96, 128}, {96, 250}, {96, 313},
{100, 1}, {100, 128}, {101, 7}, {108, 0}, {108, 70}, {108, 254}, {108,
272}, {108, 515}, {108, 565}, {109, 656}, {112, 500}, {115, 77}, {115,
250}, {125, 0}, {125, 1}, {125, 3}, {125, 4}, {125, 7}, {125, 8}, {125,
11}, {125, 15}, {125, 16}, {125, 23}, {125, 31}, {125, 32}, {125, 38},
{125, 49}, {125, 62}, {125, 126}, {125, 156}, {125, 164}, {125, 187}, {125,
194}, {125, 198}, {125, 205}, {125, 250}, {125, 253}, {125, 266}, {125,
281}, {125, 284}, {125, 296}, {125, 347}, {125, 382}, {125, 501}, {125,
507}, {125, 515}, {125, 523}, {125, 538}, {125, 554}, {125, 569}, {125,
577}, {125, 593}, {125, 608}, {125, 647}, {125, 710}, {125, 718}, {125,
750}, {125, 765}, {125, 766}, {126, 0}, {126, 1}, {126, 15}, {126, 25},
{126, 32}, {126, 63}, {126, 80}, {126, 125}, {126, 128}, {126, 147}, {126,
268}, {126, 284}, {126, 312}, {126, 437}, {126, 515}, {126, 531}, {128, 3},
{128, 7}, {128, 15}, {128, 22}, {128, 62}, {128, 63}, {128, 73}, {128, 77},
{128, 140}, {128, 147}, {128, 209}, {128, 269}, {128, 272}, {128, 281},
{128, 296}, {128, 331}, {128, 515}, {128, 626}, {128, 632}, {129, 0}, {129,
250}, {132, 0}, {132, 7}, {132, 62}, {132, 70}, {132, 77}, {132, 125},
{132, 141}, {132, 160}, {132, 281}, {132, 500}, {132, 510}, {132, 625},
{132, 626}, {132, 635}, {133, 18}, {133, 25}, {133, 125}, {133, 150}, {133,
156}, {133, 281}, {133, 343}, {133, 500}, {135, 0}, {135, 1}, {135, 10},
{135, 250}, {135, 531}, {136, 219}, {136, 375}, {136, 625}, {140, 0}, {140,
3}, {140, 7}, {140, 31}, {140, 46}, {140, 56}, {140, 87}, {140, 250}, {140,
257}, {140, 265}, {140, 282}, {140, 312}, {140, 500}, {140, 501}, {140,
562}, {140, 565}, {140, 609}, {140, 875}, {141, 0}, {141, 140}, {141, 143},
{141, 254}, {141, 281}, {141, 500}, {141, 522}, {141, 882}, {143, 4}, {143,
10}, {143, 15}, {143, 62}, {143, 93}, {143, 226}, {143, 350}, {143, 584},
{143, 633}, {143, 690}, {144, 0}, {144, 34}, {144, 375}, {144, 501}, {147,
0}, {147, 22}, {147, 257}, {150, 265}, {156, 1}, {156, 8}, {156, 15}, {156,
23}, {156, 31}, {156, 39}, {156, 125}, {156, 140}, {156, 203}, {156, 289},
{156, 327}, {156, 376}, {156, 566}, {156, 577}, {156, 578}, {156, 596},
{156, 907}, {157, 132}, {157, 156}, {157, 163}, {157, 437}, {157, 503},
{157, 515}, {157, 593}, {157, 702}, {159, 1}, {159, 7}, {159, 32}, {159,
62}, {159, 65}, {159, 77}, {159, 108}, {159, 132}, {159, 140}, {159, 233},
{159, 501}, {160, 0}, {160, 72}, {160, 77}, {163, 0}, {163, 1}, {163, 125},
{163, 126}, {163, 133}, {163, 625}, {163, 626}, {164, 1}, {164, 156}, {164,
250}, {164, 365}, {166, 0}, {166, 78}, {171, 0}, {171, 1}, {171, 54}, {171,
65}, {171, 94}, {171, 261}, {171, 500}, {172, 319}, {174, 77}, {175, 3},
{178, 1}, {178, 11}, {178, 62}, {179, 500}, {187, 0}, {187, 3}, {187, 4},
{187, 80}, {187, 126}, {187, 250}, {187, 281}, {187, 500}, {187, 518},
{187, 534}, {187, 632}, {187, 702}, {187, 750}, {187, 785}, {188, 8}, {188,
125}, {188, 147}, {188, 179}, {188, 253}, {188, 688}, {190, 0}, {190, 1},
{190, 38}, {190, 766}, {191, 0}, {191, 140}, {194, 0}, {194, 3}, {194, 7},
{194, 10}, {194, 35}, {194, 47}, {194, 93}, {194, 265}, {194, 410}, {194,
846}, {195, 500}, {197, 15}, {197, 500}, {198, 0}, {202, 7}, {202, 62},
{202, 125}, {202, 187}, {202, 453}, {202, 503}, {205, 69}, {206, 0}, {210,
0}, {210, 789}, {212, 751}, {218, 15}, {218, 46}, {218, 63}, {218, 125},
{218, 174}, {218, 257}, {218, 261}, {218, 265}, {219, 7}, {221, 0}, {221,
7}, {221, 281}, {221, 508}, {225, 46}, {225, 516}, {241, 31}, {241, 63},
{250, 0}, {250, 1}, {250, 3}, {250, 7}, {250, 8}, {250, 16}, {250, 18},
{250, 19}, {250, 31}, {250, 32}, {250, 49}, {250, 53}, {250, 62}, {250,
63}, {250, 69}, {250, 70}, {250, 77}, {250, 84}, {250, 108}, {250, 125},
{250, 128}, {250, 129}, {250, 135}, {250, 140}, {250, 156}, {250, 167},
{250, 187}, {250, 190}, {250, 209}, {250, 234}, {250, 257}, {250, 281},
{250, 285}, {250, 313}, {250, 315}, {250, 343}, {250, 376}, {250, 452},
{250, 500}, {250, 503}, {250, 510}, {250, 515}, {250, 562}, {250, 563},
{250, 565}, {250, 572}, {250, 577}, {250, 593}, {250, 608}, {250, 629},
{250, 640}, {250, 753}, {250, 769}, {250, 812}, {250, 827}, {250, 890},
{250, 921}, {251, 3}, {251, 10}, {251, 34}, {251, 38}, {251, 125}, {251,
126}, {251, 140}, {251, 171}, {251, 190}, {251, 202}, {251, 222}, {251,
241}, {251, 284}, {251, 441}, {251, 500}, {251, 515}, {251, 556}, {251,
728}, {251, 751}, {251, 827}, {253, 0}, {253, 1}, {253, 10}, {253, 22},
{253, 25}, {253, 31}, {253, 47}, {253, 62}, {253, 125}, {253, 132}, {253,
163}, {253, 195}, {253, 222}, {253, 315}, {253, 320}, {253, 375}, {253,
500}, {253, 501}, {253, 507}, {253, 635}, {253, 651}, {253, 812}, {254, 0},
{254, 135}, {254, 266}, {254, 281}, {254, 959}, {257, 10}, {257, 22}, {257,
31}, {257, 62}, {257, 63}, {257, 125}, {257, 147}, {257, 157}, {257, 250},
{257, 288}, {257, 297}, {257, 334}, {257, 353}, {257, 375}, {257, 501},
{257, 694}, {257, 757}, {258, 65}, {258, 522}, {258, 593}, {258, 625},
{258, 827}, {260, 0}, {260, 3}, {260, 254}, {260, 312}, {260, 330}, {260,
516}, {260, 781}, {261, 10}, {261, 251}, {265, 0}, {265, 1}, {265, 3},
{265, 8}, {265, 10}, {265, 26}, {265, 65}, {265, 77}, {265, 125}, {265,
188}, {265, 257}, {265, 312}, {265, 409}, {265, 500}, {265, 503}, {265,
570}, {266, 3}, {266, 156}, {266, 233}, {266, 694}, {268, 3}, {268, 8},
{268, 16}, {268, 77}, {268, 125}, {268, 140}, {268, 503}, {268, 584}, {269,
8}, {269, 31}, {272, 3}, {272, 77}, {272, 500}, {272, 632}, {275, 69},
{275, 534}, {281, 0}, {281, 1}, {281, 8}, {281, 11}, {281, 39}, {281, 46},
{281, 63}, {281, 70}, {281, 93}, {281, 128}, {281, 251}, {281, 507}, {281,
516}, {281, 569}, {281, 671}, {281, 687}, {281, 768}, {282, 1}, {282, 23},
{282, 31}, {282, 96}, {282, 132}, {282, 205}, {282, 288}, {282, 390}, {282,
503}, {282, 788}, {284, 0}, {284, 31}, {284, 258}, {284, 500}, {288, 0},
{288, 80}, {288, 140}, {288, 538}, {291, 7}, {291, 31}, {296, 0}, {296, 4},
{296, 7}, {296, 16}, {296, 194}, {296, 359}, {296, 500}, {296, 501}, {296,
508}, {296, 629}, {296, 687}, {296, 751}, {296, 812}, {297, 500}, {299, 0},
{299, 1}, {299, 539}, {303, 22}, {303, 32}, {303, 656}, {306, 42}, {312,
0}, {312, 7}, {312, 31}, {312, 128}, {312, 156}, {312, 229}, {312, 378},
{312, 385}, {312, 578}, {312, 751}, {312, 788}, {312, 910}, {313, 0}, {313,
15}, {313, 100}, {313, 125}, {313, 128}, {315, 49}, {315, 202}, {315, 593},
{315, 909}, {316, 31}, {316, 38}, {316, 327}, {316, 625}, {319, 0}, {319,
34}, {319, 125}, {319, 500}, {319, 625}, {319, 718}, {320, 19}, {320, 225},
{320, 609}, {322, 0}, {322, 10}, {322, 140}, {322, 315}, {322, 625}, {323,
538}, {327, 1}, {327, 3}, {327, 31}, {327, 69}, {328, 0}, {328, 77}, {328,
132}, {330, 0}, {334, 156}, {334, 313}, {334, 376}, {334, 508}, {334, 546},
{334, 648}, {337, 500}, {337, 503}, {338, 3}, {338, 126}, {343, 0}, {343,
534}, {344, 34}, {344, 226}, {346, 125}, {346, 500}, {350, 562}, {350,
587}, {353, 15}, {353, 500}, {353, 750}, {354, 500}, {358, 1}, {358, 299},
{359, 501}, {365, 7}, {375, 0}, {375, 1}, {375, 35}, {375, 190}, {375,
312}, {376, 15}, {376, 69}, {376, 78}, {376, 93}, {376, 250}, {376, 781},
{378, 63}, {378, 69}, {378, 382}, {379, 15}, {382, 31}, {382, 531}, {382,
640}, {385, 35}, {386, 15}, {386, 62}, {386, 159}, {386, 515}, {390, 94},
{390, 125}, {390, 140}, {390, 260}, {390, 569}, {390, 609}, {390, 753},
{391, 0}, {391, 18}, {391, 78}, {391, 876}, {393, 251}, {393, 625}, {398,
897}, {400, 3}, {406, 34}, {406, 65}, {406, 144}, {406, 327}, {406, 515},
{406, 531}, {406, 785}, {407, 3}, {409, 15}, {409, 46}, {409, 437}, {410,
3}, {413, 15}, {413, 656}, {414, 49}, {421, 109}, {421, 197}, {422, 100},
{424, 315}, {437, 15}, {437, 62}, {437, 125}, {437, 500}, {440, 7}, {440,
500}, {440, 562}, {440, 775}, {448, 0}, {448, 438}, {452, 16}, {452, 31},
{452, 250}, {452, 562}, {459, 62}, {459, 268}, {459, 796}, {468, 0}, {471,
7}, {471, 538}, {475, 109}, {476, 63}, {490, 7}, {500, 0}, {500, 1}, {500,
4}, {500, 7}, {500, 10}, {500, 11}, {500, 15}, {500, 18}, {500, 22}, {500,
25}, {500, 31}, {500, 34}, {500, 38}, {500, 42}, {500, 46}, {500, 47},
{500, 50}, {500, 62}, {500, 63}, {500, 69}, {500, 73}, {500, 77}, {500,
80}, {500, 93}, {500, 94}, {500, 125}, {500, 126}, {500, 144}, {500, 166},
{500, 171}, {500, 178}, {500, 250}, {500, 257}, {500, 265}, {500, 281},
{500, 315}, {500, 316}, {500, 376}, {500, 386}, {500, 413}, {500, 437},
{500, 503}, {500, 507}, {500, 508}, {500, 510}, {500, 516}, {500, 542},
{500, 674}, {500, 687}, {500, 718}, {500, 750}, {500, 819}, {500, 875},
{500, 906}, {501, 0}, {501, 7}, {501, 18}, {501, 22}, {501, 31}, {501, 47},
{501, 125}, {501, 141}, {501, 150}, {501, 171}, {501, 190}, {501, 203},
{501, 209}, {501, 260}, {501, 288}, {501, 500}, {501, 510}, {501, 534},
{501, 656}, {501, 875}, {503, 0}, {503, 3}, {503, 16}, {503, 42}, {503,
46}, {503, 63}, {503, 66}, {503, 147}, {503, 250}, {503, 261}, {503, 322},
{503, 350}, {503, 378}, {503, 468}, {503, 500}, {503, 625}, {504, 1}, {504,
3}, {504, 22}, {504, 77}, {504, 115}, {504, 500}, {504, 600}, {504, 789},
{504, 796}, {507, 0}, {507, 3}, {507, 15}, {507, 18}, {507, 35}, {507, 38},
{507, 125}, {507, 250}, {507, 500}, {507, 501}, {507, 547}, {508, 0}, {508,
32}, {508, 132}, {508, 140}, {508, 382}, {508, 501}, {510, 66}, {510, 210},
{510, 303}, {511, 268}, {511, 299}, {511, 500}, {515, 0}, {515, 1}, {515,
3}, {515, 53}, {515, 69}, {515, 93}, {515, 128}, {515, 132}, {515, 156},
{515, 167}, {515, 171}, {515, 188}, {515, 206}, {515, 250}, {515, 257},
{515, 281}, {515, 375}, {515, 410}, {515, 437}, {515, 516}, {515, 751},
{516, 0}, {516, 15}, {516, 35}, {516, 77}, {516, 103}, {516, 156}, {516,
296}, {516, 300}, {516, 315}, {516, 459}, {516, 656}, {516, 834}, {516,
865}, {518, 0}, {518, 7}, {518, 15}, {518, 65}, {518, 194}, {518, 250},
{518, 265}, {518, 268}, {518, 577}, {518, 625}, {518, 812}, {519, 62},
{522, 0}, {522, 31}, {522, 65}, {522, 80}, {522, 315}, {522, 376}, {522,
531}, {522, 781}, {522, 897}, {523, 150}, {523, 282}, {525, 22}, {525, 31},
{525, 251}, {526, 49}, {531, 0}, {531, 1}, {531, 7}, {531, 10}, {531, 49},
{531, 93}, {531, 126}, {531, 132}, {531, 156}, {531, 202}, {531, 218},
{531, 258}, {531, 315}, {531, 375}, {531, 503}, {531, 593}, {531, 765},
{531, 772}, {532, 0}, {532, 3}, {532, 15}, {532, 31}, {532, 32}, {532, 62},
{532, 73}, {532, 132}, {532, 562}, {534, 15}, {534, 300}, {535, 0}, {535,
163}, {538, 0}, {538, 7}, {538, 15}, {538, 629}, {539, 62}, {539, 468},
{541, 891}, {546, 1}, {546, 125}, {546, 281}, {546, 288}, {546, 319}, {546,
327}, {546, 500}, {546, 532}, {546, 539}, {546, 640}, {547, 1}, {547, 250},
{547, 784}, {549, 128}, {550, 0}, {550, 221}, {556, 15}, {562, 0}, {562,
3}, {562, 4}, {562, 8}, {562, 31}, {562, 34}, {562, 46}, {562, 69}, {562,
93}, {562, 125}, {562, 143}, {562, 319}, {562, 500}, {562, 501}, {562,
504}, {562, 508}, {562, 510}, {563, 0}, {563, 39}, {563, 73}, {563, 257},
{563, 376}, {563, 500}, {565, 0}, {565, 15}, {565, 296}, {565, 390}, {566,
0}, {566, 815}, {569, 3}, {569, 125}, {569, 126}, {569, 175}, {569, 190},
{569, 313}, {569, 538}, {570, 65}, {572, 65}, {572, 251}, {573, 500}, {577,
0}, {577, 1}, {577, 15}, {577, 18}, {577, 159}, {577, 501}, {577, 518},
{577, 584}, {578, 0}, {578, 385}, {580, 500}, {584, 625}, {593, 0}, {593,
1}, {593, 3}, {593, 31}, {593, 41}, {593, 53}, {593, 281}, {593, 633},
{593, 878}, {593, 882}, {594, 32}, {594, 93}, {594, 784}, {596, 66}, {600,
0}, {600, 253}, {601, 577}, {603, 62}, {608, 0}, {611, 18}, {616, 375},
{625, 0}, {625, 1}, {625, 3}, {625, 7}, {625, 34}, {625, 108}, {625, 126},
{625, 129}, {625, 190}, {625, 254}, {625, 275}, {625, 284}, {625, 344},
{625, 346}, {625, 390}, {625, 425}, {625, 532}, {625, 538}, {625, 750},
{625, 968}, {626, 31}, {626, 32}, {626, 34}, {626, 63}, {626, 100}, {626,
111}, {626, 500}, {626, 508}, {626, 643}, {628, 0}, {628, 46}, {629, 62},
{629, 625}, {632, 8}, {632, 81}, {632, 93}, {632, 156}, {632, 202}, {632,
547}, {633, 15}, {633, 268}, {633, 516}, {640, 0}, {640, 23}, {640, 39},
{640, 251}, {640, 319}, {640, 358}, {640, 522}, {641, 8}, {641, 343}, {641,
751}, {643, 265}, {644, 18}, {644, 41}, {648, 19}, {656, 3}, {656, 7},
{656, 62}, {656, 382}, {656, 507}, {656, 757}, {657, 0}, {657, 81}, {657,
894}, {659, 65}, {659, 476}, {659, 750}, {663, 125}, {671, 78}, {671, 253},
{672, 375}, {687, 0}, {687, 15}, {687, 18}, {687, 31}, {687, 32}, {687,
108}, {687, 125}, {687, 296}, {687, 500}, {688, 0}, {688, 38}, {690, 265},
{690, 757}, {694, 0}, {694, 65}, {694, 250}, {695, 0}, {697, 93}, {702, 3},
{702, 156}, {702, 282}, {703, 281}, {705, 46}, {705, 250}, {706, 94}, {709,
628}, {718, 7}, {718, 31}, {718, 62}, {725, 0}, {725, 18}, {733, 376},
{736, 784}, {740, 77}, {740, 126}, {750, 0}, {750, 16}, {750, 22}, {750,
31}, {750, 32}, {750, 62}, {750, 63}, {750, 115}, {750, 128}, {750, 159},
{750, 250}, {750, 315}, {750, 343}, {750, 344}, {750, 424}, {750, 562},
{750, 569}, {750, 626}, {751, 46}, {751, 93}, {751, 300}, {751, 522}, {753,
0}, {753, 80}, {753, 171}, {753, 250}, {753, 406}, {753, 562}, {757, 46},
{757, 47}, {757, 209}, {757, 265}, {757, 312}, {758, 266}, {760, 0}, {760,
8}, {761, 62}, {761, 600}, {765, 62}, {765, 148}, {765, 516}, {765, 534},
{765, 823}, {766, 141}, {766, 500}, {768, 0}, {768, 141}, {768, 251}, {768,
781}, {772, 375}, {772, 500}, {773, 0}, {781, 62}, {781, 63}, {781, 147},
{781, 157}, {781, 187}, {782, 3}, {782, 15}, {782, 34}, {782, 125}, {782,
253}, {784, 516}, {784, 569}, {788, 111}, {788, 116}, {789, 7}, {789, 140},
{789, 376}, {796, 906}, {797, 1}, {812, 18}, {812, 126}, {812, 750}, {812,
796}, {813, 0}, {813, 7}, {813, 500}, {815, 49}, {815, 96}, {819, 565},
{822, 0}, {827, 4}, {827, 125}, {827, 383}, {830, 31}, {843, 4}, {843,
281}, {846, 0}, {846, 69}, {859, 260}, {875, 35}, {875, 80}, {875, 148},
{875, 206}, {875, 250}, {875, 312}, {875, 500}, {875, 503}, {875, 702},
{875, 782}, {875, 878}, {876, 0}, {878, 31}, {878, 78}, {879, 515}, {890,
163}, {890, 816}, {891, 553}, {897, 46}, {897, 265}, {906, 0}, {906, 65},
{906, 518}, {913, 69}, {913, 197}, {937, 413}, {937, 531}, {937, 565},
{940, 16}, {941, 250}, {944, 53}, {944, 346}, {947, 1}, {952, 375}, {59, 371},
{371, 431}, {431, 564}, {564, 779}, {779, 835}, {835, 877}, {877, 986}
};
std::vector<int> results = {
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, 59, 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, 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, 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, 59, 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, 59, 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, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 59, 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, 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,
774, 0, 0, 0, 0, 59, 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, 59, 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, 774, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 59, 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, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0
};
DASH_LOG_DEBUG("ConnectedComponentsTest.Blocked.AlgorithmRun",
"construction started");
graph_t g(edge_list.begin(), edge_list.end(), 1000);
DASH_LOG_DEBUG("ConnectedComponentsTest.Blocked.AlgorithmRun",
"construction finished");
dash::barrier();
DASH_LOG_DEBUG("ConnectedComponentsTest.Blocked.AlgorithmRun",
"algorithm started");
dash::connected_components(g);
DASH_LOG_DEBUG("ConnectedComponentsTest.Blocked.AlgorithmRun",
"algorithm finished");
int wrong_components = 0;
if(dash::myid() == 0) {
int index = 0;
for(auto it = g.vertices().begin(); it != g.vertices().end(); ++it) {
auto v = g[it];
if(v.attributes().comp != results[index]) {
++wrong_components;
break;
}
++index;
}
// each component set according to results array
EXPECT_EQ_U(0, wrong_components);
}
auto & team = dash::Team::All();
dash::LogarithmicVertexMapper<graph_t> mapper(1000, team.size());
DASH_LOG_DEBUG("ConnectedComponentsTest.Logarithmic.AlgorithmRun",
"construction started");
// TODO: creating 2 graphs in their own scopes results in a segfault
// probably a problem with the destructor
// happens only in GTest though
graph_t g2(edge_list.begin(), edge_list.end(), 1000, team, mapper);
DASH_LOG_DEBUG("ConnectedComponentsTest.Logarithmic.AlgorithmRun",
"construction finished");
dash::barrier();
DASH_LOG_DEBUG("ConnectedComponentsTest.Logarithmic.AlgorithmRun",
"algorithm started");
dash::connected_components(g2);
DASH_LOG_DEBUG("ConnectedComponentsTest.Logarithmic.AlgorithmRun",
"algorithm finished");
wrong_components = 0;
if(dash::myid() == 0) {
int index = 0;
for(auto it = g2.vertices().begin(); it != g2.vertices().end(); ++it) {
auto v = g2[it];
if(v.attributes().comp != results[index]) {
++wrong_components;
break;
}
++index;
}
// each component set according to results array
EXPECT_EQ_U(0, wrong_components);
}
dash::barrier();
}