Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
21 kB
0
Indexable
Never
*** De ***
Given the map of BTS consists of N x M cells. Each cell in map have a cost and can connect to other 6 cells around it. Two cells are connected if they share a same edge.
We call a group of 4 connected cells a cluster. Your program should find the cluster with highest cost sum and print out the square value of its sum
Ex: M = 5 , N = 3
 
In above example, we have a cluster with square of sum 
(300 + 410 + 185 + 95)2 = 980100

 
In above example, the selected cells is not a cluster.

[Input]
- The first line is the number of test cases T (T <= 50)
- In each TC :
	+ The first line give the size of the map M, N ( 3 ≤ N, M ≤ 15 )
	+ In the next N lines, the cost C (0 ≤ C ≤ 1000) of each cell is given as below rule
 
5
5 3
300 410 150 55 370
120 185 440 190 450 
165 70 95 420 50 
5 5
356 55 41 453 12 
401 506 274 506 379 
360 281 421 311 489 
425 74 276 371 164 
138 528 461 477 470

[Output]
Print out the square value of maximum cluster's sum
Case #1
2250000
Case #2
3748096
Case #3
3928324
Case #4
7236100
Case #5
13104400

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

*** output ***
Case #1
2250000
Case #2
3748096
Case #3
3928324
Case #4
7236100
Case #5
13104400
Case #6
13176900
Case #7
12404484
Case #8
8277129
Case #9
11370384
Case #10
11532816
Case #11
11573604
Case #12
13667809
Case #13
11148921
Case #14
12716356
Case #15
12602500
Case #16
11519236
Case #17
16000000
Case #18
10329796
Case #19
10452289
Case #20
12278016
Case #21
10023556
Case #22
14341369
Case #23
11235904
Case #24
11209104
Case #25
10036224
Case #26
13542400
Case #27
13003236
Case #28
14714896
Case #29
10400625
Case #30
11082241
Case #31
13838400
Case #32
14730244
Case #33
11703241
Case #34
12616704
Case #35
12503296
Case #36
12096484
Case #37
12816400
Case #38
13749264
Case #39
14853316
Case #40
13638249
Case #41
14402025
Case #42
14227984
Case #43
12945604
Case #44
13476241
Case #45
14303524
Case #46
14077504
Case #47
14684224
Case #48
12952801
Case #49
14227984
Case #50
14190289