题目描述

牛牛现在有一个从小到大排好序的整数序列$\red{A}$。

他希望插入一些整数，使得相邻两两之间的差值一样大。不能插入在开头和结尾 牛牛想知道最少插入多少个整数才能满足要求，如果不能，则输出$\red{-1}$。

输入格式

第一行一个整数 $\red{T，}$表示数据组数。

每组数据第一行输入一个整数$\red{n，}$表示序列$\red{A}$的大小。

每组数据第二行输入$\red{n}$个整数，表示$\red{A}$数组中的数字$\red{Ai}$。

对于 $\red{30\%}$的数据有$\red{1 ≤}$ $\red{n ≤}$ $\red{3}$。

对于 $\red{60\%}$的数据有$\red{1 ≤}$ $\red{n ≤}$ $\red{1000}$。

对于 $\red{100\%}$的数据有$\red{1 ≤}$ $\red{n ≤}$ $\red{10^6, 0 ≤}$ $\red{Ai ≤}$ $\red{10^6, 1 ≤}$ $\red{T ≤}$ $\red{10}$。

输出格式

对于每组数据输出一行一个整数，即插入的最小数字个数。

样例

输入样例1

3
4
3 7 11 19
3
3 8 10
5
3 9 15 21 21

输出样例1

1
5
-1

输入样例2

10
74
2 4 12 19 35 39 79 92 96 110 151 209 212 219 221 226 230 251 252 271 272 319 
336 359 379 388 389 393 397 401 439 440 451 469 491 505 522 527 557 571 580 
630 637 670 688 736 739 742 747 771 794 798 799 803 804 808 813 834 837 843 
849 855 867 872 873 892 893 902 924 935 977 979 985 998
56
28 33 39 41 48 57 93 108 113 117 122 167 187 225 239 251 294 294 299 305 308 
314 323 369 425 431 450 482 503 504 539 542 550 584 613 645 664 699 703 707 
711 722 725 749 749 782 824 844 863 869 879 892 906 927 939 967
76
6 9 15 36 48 53 55 80 120 122 128 167 183 245 246 270 285 288 294 297 313 
324 342 360 378 394 396 406 429 443 452 468 469 475 488 495 520 562 580 581 
584 590 593 608 645 656 658 665 667 669 670 676 683 720 736 739 742 755 783 
803 807 808 815 836 872 874 878 893 915 934 935 939 943 963 980 988
14
42 125 161 234 250 268 285 296 585 600 607 682 699 998
15
429 452 475 521 590 613 636 659 682 705 797 843 889 912 935
76
2 22 34 69 83 88 130 132 138 155 158 169 187 189 202 221 230 244 251 264 286 
291 295 302 321 322 350 352 359 375 381 384 386 394 396 404 488 489 490 496 
501 514 525 527 556 594 616 629 674 686 687 697 699 745 748 776 797 809 810 
811 818 820 821 824 835 858 868 871 913 921 923 929 934 953 974 977
38
419 441 474 485 507 518 529 540 551 573 595 606 617 628 650 661 672 683 694 
705 716 738 782 793 804 815 826 848 859 870 881 914 925 936 947 969 980 991
64
127 136 154 172 181 190 208 226 235 244 253 271 280 289 298 307 316 325 334 
370 388 397 415 424 442 469 505 514 532 550 568 577 586 595 604 613 622 640 
649 658 676 685 703 721 730 748 757 766 784 802 820 829 838 847 856 865 883 
910 919 928 937 964 973 982
146
560 562 564 566 570 572 574 576 578 580 582 584 586 592 594 596 600 606 610 
614 620 622 624 626 628 632 636 638 640 642 646 650 652 654 658 662 664 666 
672 674 676 682 684 686 688 690 692 694 696 698 706 710 712 714 716 720 722 
724 730 732 734 740 744 750 752 756 758 762 766 770 772 774 776 778 786 790 
796 798 804 806 808 812 814 816 822 824 828 830 832 836 838 842 846 848 852 
856 858 860 864 868 870 872 874 878 882 884 886 888 890 892 894 900 902 904 
906 912 914 916 918 920 922 924 926 934 936 940 942 944 946 948 950 952 954 
956 960 962 968 972 974 976 978 980 982 986 990 996
4
113 603 895 909

输出样例2

923
-1
907
943
8
900
15
32
73
395

提示

样例 $\red{1 }$说明

对于样例 $\red{1，}$可以填入一个 $\red{15，}$使得$\red{(3,7,11,15,19)}$相邻两两差值为 $\red{4}$。

对于样例 $\red{2，}$可以填入$\red{(4,5,6,7,9)，}$使得$\red{(3,4,5,6,7,8,9,10)}$相邻两两差值为 $\red{1}$。

对于样例 $\red{3，}$无论怎么插入都无法使数组相邻两两间差值相同。

样例 $\red2$ 说明

该样例为大样例。