307
999 119
7 1427 0 437623
9 1009 282733119 282603
9 1217 473062507 388712
6 1047 132150302 129451
7 748 52 1
7 1035 147664491 142671
4 916 489 2
1 1182 718035456 607475
7 959 34 1
2 762 449 2
3 733 242 1
6 1510 39742927 625556
4 1182 205851671 860661
1 1361 396387171 291247
7 1296 1000000000 904514
9 1268 45995442 36274
1 1059 360792585 585095
4 1206 1000000000 958641
9 360 62 3
5 603 894 1
7 1068 926072413 867109
2 380 1312 3
4 1207 1000000000 839157
9 1043 550684192 527981
2 1662 140768787 754043
3 1665 723953827 547094
1 1290 860132198 732715
7 1244 66038600 54926
1 1308 1000000000 990942
8 905 2691 2
8 1318 1000000000 910028
7 1540 32669176 22646
7 1495 962353429 859492
2 1446 602279959 502859
4 1250 212286097 299829
7 1290 484728278 438213
7 1008 57786606 330293
6 1438 557352927 556150
10 1635 1000000000 947444
3 1006 289145943 288848
2 451 146 1
1 1645 875411729 539125
3 1565 1000000000 982145
10 1530 171150400 111863
9 1204 1000000000 902805
10 1320 767050681 581099
9 1627 1000000000 647513
4 674 509 2
9 722 280 1
10 444 399 3
5 1220 77600549 63607
9 1615 1000000000 836932
8 1191 927098573 820607
5 1077 185560863 174836
2 1324 281979072 241573
7 675 650 3
10 1464 486576749 436502
3 1098 112551887 109112
3 1358 759822337 635280
4 1447 674514713 466147
6 1647 384298636 258464
9 1484 182309538 777818
6 1218 145279388 119277
6 1115 171339181 158110
8 1518 1000000000 968985
8 1304 643166714 493226
4 1016 35842455 35278
2 1590 663033190 417002
6 920 736 2
5 1509 168759151 128338
2 349 1807 3
5 529 1787 3
5 1095 329250085 300685
6 393 284 2
10 1376 656168550 616278
1 476 999 1
3 716 215 3
7 1283 282714826 269938
2 701 488 2
1 635 938 3
9 1513 527582998 409328
3 361 169 2
3 976 346 3
1 1422 1000000000 922872
9 1109 280513795 252943
9 337 140 1
10 1171 537566897 527017
7 1106 879475589 817245
4 1510 788974074 643398
7 1375 162899924 138556
1 448 514 3
6 675 582 3
8 776 251 1
5 1635 480892744 294124
7 544 462 2
7 608 631 3
2 1191 38485980 32314
6 1162 399815156 344075
1 1421 769889740 627822
8 1531 111914574 73099
9 723 581 3
7 533 78 2
1 1069 85603385 80078
5 645 1445 1
4 1447 1000000000 737544
1 1392 1000000000 845741
2 1637 239976266 200310
5 425 1135 1
7 1271 115458918 90841
6 1059 109613916 103507
2 1373 474403086 345523
7 871 25 1
3 1329 111889844 84191
3 1100 135788401 123444
5 1015 439341306 434673
8 1388 498024879 477206
5 348 350 3
7 1572 263831914 167832
8 1075 902356083 839401
9 1321 329355687 249323
10 1082 624310764 576997
4 1056 563369671 533494
6 1265 279757919 275913
9 845 265 1
8 1072 506514646 472495
2 1319 421071453 352224
5 996 148 2
7 1229 8188831 6663
2 587 566 2
4 1283 83132774 75138
5 891 722 2
3 1356 1000000000 975628
2 1229 243362930 205292
2 466 211 1
1 887 3652 3
3 1597 748718448 888748
6 492 557 3
1 1658 321428509 225196
8 695 21 1
6 1588 64407723 46498
8 1597 950960971 854491
8 677 359 2
2 563 481 3
9 905 322 1
4 1165 391287387 335869
2 917 422 1
1 1505 269590658 179130
8 862 534 3
7 1064 577092548 552905
5 1204 593536205 527008
7 528 226 1
9 1016 412378149 405884
10 1084 576554670 531877
6 361 53 1
4 1634 182749834 111842
3 1127 1000000000 921532
9 726 1464 1
5 1144 964313982 942522
2 1492 1000000000 750648
7 1402 299666925 534092
5 1422 1000000000 792119
5 1365 463910268 339861
4 1046 83685234 80005
10 1408 730995814 800222
9 1441 354095985 316231
7 1183 1000000000 925753
7 1456 557004450 382558
5 1540 987071261 926895
7 1474 323503743 305760
6 1437 830282796 577789
4 1047 653072538 623756
6 1225 958636650 834120
10 842 771 2
5 712 148 1
3 727 140 1
10 449 29 3
6 382 348 3
2 1456 98244932 89248
9 1084 735541697 678544
8 1026 749540923 731056
9 809 1679 2
10 1662 373444774 243205
5 1418 639063467 537171
1 1067 853545586 799949
5 1646 508428007 308887
8 517 24 1
5 1372 394257449 575615
9 1092 626210678 573453
3 473 34 3
3 1350 208164605 154196
4 793 176 2
1 1531 1000000000 821671
6 392 1580 2
1 373 63 1
10 1110 676243086 609228
2 1007 681434013 679751
6 682 783 1
7 418 157 2
10 998 327 1
5 386 363 2
3 1384 860331770 621627
1 545 226 2
2 1413 646138061 457281
1 1455 269815789 267533
2 1225 134569929 109853
3 1211 482557854 757068
2 444 189 1
6 1160 155596049 134573
8 480 239 1
2 1214 686286607 679303
9 775 121 1
4 619 1549 2
10 421 158 1
5 1272 532780435 491807
3 1272 906748624 794156
9 725 297 1
4 979 482 1
4 1541 346798619 321601
3 1017 493845037 485590
10 1289 62409590 55375
3 1242 194633821 156710
9 972 171 1
7 1066 841775737 818211
6 439 133 1
8 1327 1000000000 948132
5 1412 207285248 862919
6 1499 948450285 632722
3 1218 522664509 429117
2 487 53 2
9 482 452 2
8 1660 66903094 43440
4 1463 1000000000 869886
3 1090 761948977 703829
7 1061 790986912 773472
9 1202 475559281 395640
2 1535 85339356 563146
8 1380 248812621 180299
9 1323 717082470 594300
2 1442 1000000000 836262
10 608 384 2
1 476 182 1
2 1233 68784433 56265
3 1635 120785236 335679
4 1513 404381292 361375
7 374 355 2
5 420 329 2
4 1629 248267577 216197
4 818 733 2
1 1597 978973783 613008
9 1557 826612017 626615
10 1039 290501740 284968
6 1475 230623470 229199
7 1543 1000000000 723546
10 1082 735279594 679556
2 1052 359279041 341520
1 341 143 1
2 723 26 1
8 639 564 2
9 1264 1000000000 874830
7 769 41 1
1 1385 715182888 700372
9 899 339 1
4 1188 629607969 536819
6 1309 821825544 627827
7 1210 914966966 827312
5 541 116 1
3 1301 367850926 336037
6 417 38 1
2 1521 651642245 643953
2 1338 263582516 233979
3 1034 823774405 824548
1 558 107 1
6 432 39 2
2 494 119 1
3 1141 193992827 170020
6 1383 422936617 305811
8 1319 1000000000 799595
9 1654 629462859 595933
8 498 307 2
2 1006 340269781 339781
10 799 508 2
8 1256 174507387 138939
3 1211 434637511 371798
2 1175 774190480 757345
8 911 382 2
8 1478 216642291 146578
9 1480 212667125 143694
10 1612 1000000000 794072
9 1305 343981217 307591
6 1602 369352322 230557
8 1079 890225722 825047
6 400 397 2
5 1472 929013317 711247
2 1523 231231804 153575
2 1401 652538174 465766
6 715 205 1
9 1548 1000000000 661221
10 1104 459654820 416354
4 1182 91396714 301519
4 1113 65406559 58766
7 1329 888166719 668297
7 1060 127493628 120277
3 1307 482578821 444683
7 346 131 1
1 1654 1000000000 643818
5 1661 115349684 84952
2 761 95 2