use malachite_base::num::arithmetic::traits::{
CoprimeWith, JacobiSymbol, KroneckerSymbol, LegendreSymbol, ModPowerOf2,
};
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::{One, Two, Zero};
use malachite_base::num::comparison::traits::PartialOrdAbs;
use malachite_base::num::conversion::traits::WrappingInto;
use malachite_base::test_util::generators::common::GenConfig;
use malachite_base::test_util::generators::{
unsigned_pair_gen_var_27, unsigned_pair_gen_var_40, unsigned_vec_pair_gen_var_32,
};
use malachite_nz::natural::arithmetic::kronecker_symbol::{
limbs_jacobi_symbol_init, limbs_jacobi_symbol_same_length,
};
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;
use malachite_nz::test_util::generators::{
natural_gen, natural_gen_var_8, natural_pair_gen, natural_pair_gen_var_12,
natural_pair_gen_var_13, natural_pair_gen_var_14, natural_pair_gen_var_4, natural_triple_gen,
natural_triple_gen_var_8, natural_triple_gen_var_9,
};
use malachite_nz::test_util::natural::arithmetic::kronecker_symbol::jacobi_symbol_simple;
use std::panic::catch_unwind;
use std::str::FromStr;
#[test]
fn test_limbs_jacobi_symbol_same_length() {
fn test(xs: &[Limb], ys: &[Limb], s: i8) {
let x = Natural::from_limbs_asc(xs);
let y = Natural::from_limbs_asc(ys);
assert_eq!((&x).jacobi_symbol(&y), s);
assert_eq!(jacobi_symbol_simple(x, y), s);
let bits = limbs_jacobi_symbol_init(xs[0], ys[0], 0);
let xs_orig = xs;
let ys_orig = ys;
let mut xs = xs_orig.to_vec();
let mut ys = ys_orig.to_vec();
assert_eq!(limbs_jacobi_symbol_same_length(&mut xs, &mut ys, bits), s);
}
#[cfg(not(feature = "32_bit_limbs"))]
{
test(&[0], &[1], 1);
test(&[0], &[3], 0);
test(&[0, 0], &[1, 1], 0);
test(&[0, 0, 0], &[1, 0, 1], 0);
test(&[0, 0, 1], &[1, 0, 0], 1);
test(&[0, 0, 1], &[1, 0, 1], 1);
test(&[0, 0, 1], &[1, 1, 0], 1);
test(&[0, 1, 1], &[1, 0, 1], 1);
test(&[0, 0, 1], &[1, 0, 2], 1);
test(&[0, 0, 1], &[1, 0, 3], 1);
test(&[0, 1, 1], &[1, 0, 2], -1);
test(&[1, 0, 1], &[1, 1, 3], -1);
test(&[0, 0, 2], &[1, 0, 1], 1);
test(&[0, 0, 3], &[1, 0, 1], -1);
test(&[0, 0, 2], &[1, 1, 1], 1);
test(&[0, 1, 2], &[1, 1, 1], 0);
test(&[0, 0, 3], &[1, 1, 2], 1);
test(&[0, 1, 2], &[1, 0, 3], -1);
test(&[0, 0, 0, 1, 1], &[1, 0, 0, 0, 1], 1);
test(&[0, 0, 1, 1], &[1, 1, 0, 2], 1);
test(&[0, 0, 0, 1, 1], &[1, 1, 1, 0, 1], 1);
test(&[0, 1, 1, 0, 1], &[1, 0, 0, 1, 1], 0);
test(&[0, 0, 1, 3], &[1, 1, 0, 2], 1);
test(&[0, 0, 0, 1, 1], &[1, 1, 1, 0, 3], 1);
test(&[0, 0, 1, 0, 1], &[1, 1, 0, 1, 3], 1);
test(&[0, 1, 0, 1, 1], &[1, 0, 1, 0, 3], -1);
test(&[0, 1, 1, 1, 1], &[1, 0, 0, 1, 3], 1);
test(&[0, 1, 1, 1, 1], &[1, 1, 0, 0, 3], 1);
test(&[0, 1, 0, 1, 2], &[1, 0, 1, 0, 1], 0);
}
#[cfg(feature = "32_bit_limbs")]
{
test(
&[
1873633918, 123030658, 719377342, 1504696614, 2362755734, 3961478485, 781485753,
1658134515, 2113542903, 2810709120, 516343343, 592412664, 389523939, 1066227422,
3298185546, 503562514, 201347799, 3837685524, 1791253076, 2719252242, 3220584319,
2228118840, 2873093023, 3277574845, 4183085011, 1024538582, 1879444551, 4131206800,
1120880147, 693962231, 3607359350, 2707994236, 1776336830, 1261880384, 4191042108,
2802674416, 1093640235, 1117222130, 4191804349, 488263639, 4196953979, 2945863127,
3796408273, 3918535658, 3739145025, 2025532414, 3908394825, 3730013238, 3918858199,
2236390519, 304075529, 588039508, 464824988, 1043329929, 4024659213, 777233325,
2754590310, 430183448, 2116763050, 2194568215, 3983851431, 3079663737, 3609827959,
3165570624, 3778786312, 2207000505, 494983090, 4061038956, 1847009994, 1374726069,
2216864799, 287045089, 1522632156, 3701999684, 628940848, 3777561277, 1853948570,
2149163542, 3146560430, 2662015036, 3673560784, 3148979133, 1498637710, 647923219,
512319396, 3874841555, 2725763682, 705802490, 955850189, 1466834834, 2958146031,
974815424, 3925846741, 3990055262, 2385857769, 1785254473, 975242909, 1640367194,
17679830, 2162917366, 833169313, 3823256168, 3933828973, 3314871585, 801976468,
3300008476, 189067881, 968522820, 701167717, 3456031850, 3807893479, 3883967676,
3397552960, 1177591619, 2235569799, 373301573, 874195563, 2179365380, 2119067928,
2720245803, 1010696918, 1442726415, 1066758009, 2565507481, 2473976884, 3393774679,
3952059313, 3757956916, 3261899893, 2443126808, 1361119172, 2208060333, 3775473672,
3653607071, 1293439175, 435448758, 3990892991, 1286144898, 2494049465, 2398440308,
3756264187, 4812695, 25801943, 226806926, 3042686908, 1989123535, 3254845113,
919895168, 4209027670, 4166349537, 148522488, 973817508, 3765422389, 2523318742,
579963969, 2098988831, 1365027916, 3658076322, 1733252939, 1043406512, 717910858,
2103188848, 3566233409, 1012130235, 1855787810, 156497531, 1958213821, 715897916,
4210647949, 1362164018, 3523905136, 678285695, 893316222, 4002270604, 2743748491,
1734398700, 4013187857, 3355679131, 3312607834, 671835519, 151753042, 3175422619,
2357087390, 1388249743, 3345521534, 2885692694, 3727953305, 210133499, 1091341046,
3272930824, 2473688375, 643815394, 2815077147, 3640266733, 1129170891, 591859561,
92728385, 1710489516, 2247919245, 3303371411, 2878106269, 3299382591, 6838220,
2207248685, 1067399745, 3227744596, 706680457, 347073425, 2315288352, 3459009392,
369508525, 2058436577, 723699746, 1636431631, 1393077501, 4220412446, 1818976107,
1429834151, 1320074954, 1810726444, 4038059510, 3467618009, 320963964, 1111140807,
3131364647, 1235553534, 16798724, 19240978, 2108447774, 143304067, 1703667778,
861127847, 1186666148, 1478800880, 1170455588, 2625617857, 488704999, 2402011494,
1397588188, 3587645117, 379450888, 2093883128, 1089613602, 1380578556, 3780609811,
2264391031, 1078858400, 2436761299, 3025683539, 4068664961, 3262585229, 710877465,
3189533901, 3423405972, 4226527191, 1281614997, 11582026, 4187361634, 1934508614,
2978905528, 3811137180, 254480797, 3957068379, 276691084, 980502794, 2333498429,
2402962021, 1968336748, 937179998, 328237312, 3105135306, 2708438479, 807396072,
4090616190, 338836192, 3493021773, 1007932634, 989046118, 475565105, 4280477458,
2889310878, 506168430, 2744969090, 1717140865, 180101187, 3946998676, 3256792444,
1651611832, 2217469837, 639375671, 3754995303, 803291429, 559260186, 3312276405,
1307739531, 637914444, 800094865, 1566616440, 8698228, 205523792, 1663664157,
4012170144, 1845279876, 414628822, 2589258003, 2046627153, 4252798243, 888708228,
1078803694, 2357638662, 4007813553, 2748056828, 1261654782, 3168764324, 1241689206,
2318873504, 376674550, 1961382315, 3250714815, 47982921, 1081086646, 2017910660,
3376874155, 3907817672, 3337262433, 2781215129, 700917261, 3986793763, 603713597,
2286652653, 2487070286, 3503515107, 3549521582, 2229840842, 106670130, 2152342444,
2614172954, 2980612046, 1711600105, 3367600130, 224267645, 147721273, 3762102334,
909656137, 2765963499, 1287501967, 3853510171, 2602535793, 687227193, 3372261235,
2071559967, 2243249886, 1302529466, 1536608166, 141064408, 1798146420, 1490894727,
4069708793, 539834647, 3483430067, 3470554577, 1125163274, 1002230975, 782459269,
1965180788, 1031655683, 957046550, 1927934983, 1014977728, 748904605, 1278878668,
3257529883, 1525236512, 3452233244, 595919552, 3284927605, 3947267553, 990044496,
2645462059, 3185056815, 3364504564, 2742517875, 2254394076, 256336642, 2622723662,
2255022161, 307535959, 2740603712, 326158350, 4134908299, 2331131321, 2268360042,
1661560181, 296127993, 65765671, 2991972277, 3942011917, 2155904650, 2798972906,
19922601, 336740766, 2370937438, 2954540796, 1662173899,
],
&[
1077171533, 3384534038, 3509377481, 3012981171, 2169372009, 3568066367, 510541737,
360351115, 1116770051, 2058732872, 3226198045, 1078176389, 2950624729, 812262025,
1430083408, 61306667, 64349919, 2388720201, 2804807299, 3487065571, 1162686670,
2184575935, 1234374819, 3462973209, 2204618738, 1955732567, 4274764191, 487910035,
2794693464, 1455130957, 2647605728, 4211289912, 3386405281, 117329687, 3432428417,
1300225461, 3461206919, 449524200, 904979455, 3971171435, 441380375, 1283836003,
2682594354, 1152961793, 1318795928, 308922730, 628004645, 1003117196, 1035594263,
3028460626, 3737759554, 3080878651, 2013071269, 157811103, 3209212678, 1794098871,
1571763958, 4118994167, 3323265833, 2779923965, 1781531454, 3074442432, 1330835008,
231050954, 1972822306, 3779389322, 2550908177, 1122947161, 2607600449, 2966179614,
1165225297, 4222222976, 1020266087, 1019514006, 53769477, 62821411, 3078440286,
2087323177, 4209236301, 146146381, 453393163, 4244430148, 624415024, 2096395426,
1915435196, 3779399544, 3641826296, 4157323023, 4049792386, 1892149154, 2185863226,
1046224168, 3568999985, 982204298, 154455361, 2605934809, 2605177974, 1652215061,
3058430834, 1573346022, 3979000833, 1424146496, 758475042, 3880559465, 3331749655,
4009275982, 309023272, 343958017, 2544085697, 1960862631, 1082361995, 534185037,
331011064, 3662295811, 3280920837, 2366184597, 1029851460, 1149922348, 3242309342,
3498011365, 1869617138, 2033933372, 2449772239, 1769059102, 552671522, 2541136194,
1837261562, 3331388737, 3882095076, 2111080116, 3488393361, 3110154197, 2503543094,
276095820, 109038743, 3401659741, 2955647843, 3730124703, 4288579615, 2840357519,
433563482, 3742367408, 2287152115, 3054337338, 2305325930, 1838329967, 1117989732,
2731369203, 427022429, 1959348870, 107371881, 1378273431, 3969746745, 137314119,
3494302009, 2316521941, 1304670415, 2017956904, 3960566359, 3950960171, 2483760563,
3248620299, 1282201932, 2666453601, 290925463, 1315172510, 2244058356, 83064665,
2794575253, 2751020494, 86251099, 1497864163, 1309606664, 918139255, 2382232313,
3431694285, 4197334044, 3779739436, 2597050321, 4053750034, 1347898240, 2068381165,
530540195, 777294114, 1563424547, 714733079, 251090961, 1222614986, 409927269,
2552943554, 3813553790, 2619995688, 2754487462, 1001623689, 4043538191, 780110724,
2756539090, 2640687797, 2974350673, 1702213372, 2898669867, 232176052, 2414666354,
300281312, 3252747308, 2375533144, 3579260801, 3856594937, 226065085, 2855017957,
4106625762, 4251800319, 271717704, 796181594, 2015816818, 572129733, 1578027849,
208352494, 3329313861, 3272451839, 1390383564, 3754291474, 1022210892, 3402379185,
1055267474, 2105880379, 1377373336, 2125916506, 3713096588, 3227913500, 593660170,
3662162553, 948899397, 3959019656, 743736078, 561608271, 4154259253, 753202703,
3057879152, 4093431092, 2849520862, 1298183896, 1072767461, 3844624206, 1553109174,
2211737614, 2944064724, 1134344972, 2846368205, 2535247938, 1454739286, 1408186915,
3022639671, 2985835925, 1242350664, 856614531, 3277904750, 2435844371, 2288413570,
1941580081, 2330069009, 3763753263, 1617186357, 3858822820, 3899619764, 957776791,
2415934649, 1903499570, 362345092, 3162421697, 857308796, 2166848441, 2794392063,
2916482641, 547554093, 393697940, 319583576, 3206427070, 3502792667, 3979846702,
3580352012, 3854879140, 3646613450, 4113031775, 856333171, 1029998771, 2090645466,
3125086584, 2494710984, 3249027001, 3828101842, 4278721100, 2901896440, 3549366611,
2066085974, 3815811960, 2980213693, 2418009668, 4168963107, 1522903282, 3921187989,
209293309, 1026651789, 3652402308, 1723212287, 3005358245, 3972955479, 3432513818,
1135457591, 2609451544, 1728509125, 1610815908, 1281322374, 2308282400, 1650462965,
785788526, 3039230497, 1454810597, 2847801652, 868324593, 2811238675, 1592440137,
2837082164, 2293886194, 108023352, 1338057151, 867454780, 660204887, 2727424012,
3251699301, 2307270502, 3508727390, 444210859, 4112897129, 1692014843, 232384981,
3746950478, 2035293041, 832494472, 4167968781, 2088468820, 1082123254, 2004377194,
739887690, 3903970376, 3917684808, 2220241302, 1623595193, 3168893289, 1380144222,
3245294302, 1942246969, 1017235276, 1075796476, 1420638313, 2370978268, 3571300703,
2818383559, 3979048442, 4070073076, 3639658932, 2458302928, 1936855091, 1097653713,
2517446959, 395058431, 2490534065, 3621579656, 537422087, 820775047, 1621745064,
4147607605, 773085439, 150346009, 3309770346, 623052976, 223120997, 1047915001,
2440220896, 2701090680, 682463717, 626719149, 2752394251, 2245504316, 3599570937,
1008202886, 3061625147, 3833145985, 2287104975, 3419855448, 542949621, 2260871982,
3411141468, 1089194931, 3865896761, 1906114014, 3523746087, 3034843700, 3980408914,
1779312499, 2670385907, 3943945115, 3040560985, 968208310,
],
-1,
);
test(
&[
3557994669, 445289342, 1108435216, 1656651402, 3854541936, 2345816964, 2732613883,
1181815769, 560246346, 2217942797, 3034747849, 2128803109, 193138609, 1787921939,
785846271, 690755, 4293433511, 1146911147, 4050052816, 826026913, 3182494773,
3156626600, 1014266169, 3323102091, 2921068424, 476686040, 7910507, 654440565,
3535711772, 3930398141, 4128513830, 2598121764, 4062960176, 3972780227, 855940423,
2256067460, 392376529, 2033808759, 3816270018, 1855458657, 2715891121, 3669089929,
3731047748, 1721938090, 2227294219, 3031269426, 1551726027, 3859144725, 4149437041,
3000994525, 3261175418, 2833753411, 4060863432, 2716969708, 4189891569, 677103308,
1365006263, 3293330016, 1768027889, 545258844, 2935866981, 250251281, 3680035401,
2700291474, 594423218, 898497607, 887621248, 3695367571, 2120585809, 1695812396,
645346742, 1835776782, 3264740207, 3486429797, 4208339033, 72066698, 2225784172,
1683577015, 3001910364, 3707465962, 1815190269, 124430948, 1869715335, 1801604000,
213381934, 3130033208, 3564635797, 474180177, 4240626321, 2076460830, 3656363137,
1132903283, 3991161472, 3821161503, 1744455617, 1045140442, 3902771928, 781148403,
2357356142, 3040623797, 2619406559, 195467574, 641531975, 3441001365, 114745412,
4134746228, 1311731821, 3461413652, 979311481, 1305256219, 977408510, 2999824757,
440721333, 3844175796, 1924795791, 3120129120, 532972790, 165893187, 4147094465,
3990693806, 2964895445, 1000735990, 331761162, 373581533, 1064345288, 1266123883,
2040591269, 1523811553, 2568191458, 2481902226, 2320866160, 1436736, 4008889052,
1280546217, 2098385450, 4119408023, 411283261, 3289104101, 3425489515, 2456862903,
2125542000, 1789202658, 497535957, 417045728, 3331787711, 3672146250, 1403849606,
1158118016, 1513052203, 1137714766, 4254706104, 2031746768, 1359724368, 3803765572,
422159546, 898111315, 2724325274, 1627832336, 1830223095, 4270287508, 1215166891,
2436306311, 907260779, 4034312884, 1698645062, 1078681555, 3198597175, 1586826465,
2046732632, 66062249, 3358599308, 232196012, 629981202, 935508892, 3170800564,
2191875696, 2503459156, 447871479, 3269004498, 2153827076, 267450909, 1520769342,
1163927607, 2575984589, 2978684947, 1813055270, 431843507, 226606783, 811301393,
2458665352, 585771839, 2841530354, 3556530842, 2435178025, 2845793940, 3637609260,
406241340, 144056695, 3122547306, 2101164412, 3905238054, 318269719, 3253726651,
1443434883, 178618945, 153042080, 2023190013, 2275803876, 2774886429, 3703342339,
2715860001, 1015326289, 2988607429, 1091753318, 1280790766, 779483175, 4181404689,
797271578, 3837324542, 965653269, 3998678544, 3707299808, 518493388, 2081242998,
565821490, 1370788325, 3775338190, 3238414037, 576068479, 2735674700, 1184491085,
4009553275, 3572635037, 1243646536, 2911509472, 2973906905, 1907167846, 1458306202,
2123107667, 989552556, 436261057, 605573158, 3483230043, 2880983042, 4168409866,
4019136255, 4253327858, 2651830192, 17400570, 109318954, 2078546974, 3534044718,
346014829, 3754708985, 592559018, 1742898159, 33427990, 856129692, 2342055152,
1941602123, 1408405136, 894595226, 2387883501, 3646482099, 3519957459, 2080906515,
1904107628, 3069440838, 3932421765, 3266993370, 4136525054, 4220115422, 788731893,
1686867215, 1519823776, 2877756565, 3793887677, 329226793, 3893797702, 3583826624,
1694823997, 696220909, 3611742558, 3078864649, 3766315815, 1632326088, 2654432468,
3981882671, 2280957273, 793625459, 1157977495, 1441316728, 197154581, 1561124715,
4189778267, 1333945477, 3967181114, 1421232429, 3533069272, 887767315, 2239652930,
1638811648, 3473233699, 1181657596, 3085652783, 1287675993, 2455078898, 1233237192,
2458447943, 204196519, 3524654715, 336439681, 3814153229, 3678776643, 2407863111,
2675325179, 2161593579, 1925372399, 675067792, 2605820490, 4256815185, 1323539594,
426745374, 715074163, 582328134, 2873514058, 2781239268, 466361343, 4220762639,
3844401378, 588421780, 899607035, 1173758884, 3529587577, 4191404586, 1689668754,
339535512, 11588832, 81658456, 477141048, 206734791, 3326055602, 1891545837,
117975561, 2547113968, 873099055, 682751521, 398130815, 2348739960, 182088623,
1296089616, 2510361486, 3939228547, 977564178, 3496437434, 1651453093, 2664075234,
4143568438, 387896255, 3402931396, 289202123, 2509994131, 385929339, 1853496317,
3349095771, 3744525316, 2501099484, 1571812210, 744319117, 1974272901, 862213254,
1175782054, 1175784197, 3493591642, 3451744657, 933240322, 2199334346, 2473006426,
1633463866, 448919678, 1987732235, 475336389, 2531498167, 2845909593, 672719533,
3917070486, 3812486327, 921951784, 935351493, 880449089, 3861127468, 2856437655,
1122235431, 1105796631, 1824141540, 3552996529, 1526795410, 634765135, 2225592783,
1934399617, 3018228838, 2932938217, 4119878576, 2645355264, 2039885213, 4107872338,
2577396222, 1300242611, 1610879235, 2886027894, 83647147, 1142510940, 1637400124,
3325978372, 1118962329, 1227985700, 4176365484, 4116884066, 93911175, 1843931255,
3241661048, 2946824243, 4229518060, 4153977648, 1821838858, 932057741, 3403948153,
681930575, 345042433, 3238398483, 3522674175, 1511145458, 2225511649, 1601323695,
2734513014, 2978365108, 1606989364, 946945525, 1990882013, 3195215258, 3914587165,
2448441155, 1748490947, 2249032459, 1619210750, 1164959769, 2865145797, 3737266053,
3035927303, 2962530478, 265946106, 833476822, 666127741, 3717419208, 2958451448,
244770831, 1823748962, 3500566168, 2067490898, 3303161181, 2858054390, 4069571771,
3028106864, 8735465, 3953855297, 659633477, 2990915486, 3679301885, 1463896161,
3797786358, 2022879581, 2799640567, 2175987369, 3245839346, 4240563036, 2551089091,
],
&[
1659959583, 2904634437, 335609799, 4208083935, 2129829927, 3164938818, 1437094842,
4128695178, 776066331, 3206868490, 256975577, 3354430510, 2140456023, 4193571596,
4266016240, 1376301017, 506915445, 4013967736, 3657139290, 223860627, 3175388958,
599853167, 725799221, 4128800655, 1480213210, 175078040, 1886675185, 1738455879,
2008734389, 1737895694, 2834508091, 1703658096, 3507753057, 3993341225, 568791580,
1023600771, 874605814, 65887225, 30573824, 2705597852, 2665836303, 3561654523,
3508037727, 1392125564, 3754257083, 2020933944, 4083241095, 4072208472, 2907998249,
1804340494, 3200608953, 577970893, 486672367, 1814354067, 3513024420, 1138655286,
1536324596, 4110629631, 2808131793, 69933854, 2475345926, 2887472024, 4116014864,
4018460348, 608873722, 3537176373, 3911227381, 3805837398, 1420242961, 1313695988,
1355817019, 764772441, 1215440552, 2083287207, 642044699, 921046423, 2265142632,
906587028, 174772424, 4104145270, 4199953868, 717960181, 2001049957, 2366068998,
2336245127, 2655659318, 782347589, 3183312496, 3382146064, 4213611770, 2427981515,
1765643471, 3126151525, 1453973803, 3252697014, 1560005976, 855968672, 1728830740,
3385306541, 177162479, 1024782804, 268504726, 1300885248, 1892046392, 1894377755,
3334999753, 780888935, 152771001, 66154343, 753130677, 1724675242, 3416975300,
2011564755, 3092786038, 1173839777, 502502924, 3514522395, 3492457582, 1655067969,
298388618, 1507409745, 4042261481, 1925841276, 514542391, 3251704090, 1720846063,
1424865256, 3297538873, 1875557160, 3572248143, 3236552016, 618425118, 1198410399,
3256702606, 2084542045, 3780234755, 2145950572, 97693459, 544125496, 4169732002,
2879169387, 3259419966, 2845079327, 1681321406, 553984684, 1625241374, 3667423846,
3512256822, 179220058, 3368809252, 940925092, 2204117315, 911144717, 3702475909,
1079496526, 3502765039, 1331463976, 1674009176, 4251763704, 475983445, 3375462610,
2031227825, 405099033, 101760435, 2599463798, 2175561479, 253471718, 2996294940,
612011453, 736609471, 1270127612, 928651447, 832132468, 1202045767, 1512660791,
1685269400, 1866039474, 3003538147, 1306427040, 2419401400, 2727784058, 2592708024,
1060360987, 3688549328, 3939457653, 213067692, 1791205457, 2313629636, 2382874156,
2897125589, 3092816471, 1459440010, 140615575, 3161769034, 1594344003, 4022901885,
3044761935, 2388083845, 3637404570, 3671760657, 3492650532, 2761768206, 3954822945,
112327455, 3219134020, 1811940545, 1378571471, 3747780753, 2264252238, 2008656851,
2223880320, 858157798, 1785441029, 2737890036, 4190598099, 3967960030, 4007684525,
2861863392, 2650800814, 1535056048, 2444559101, 196252521, 1487672921, 1520614795,
3333508154, 3661606593, 629421626, 358772008, 4003360989, 2950979293, 931493453,
3325437104, 3144184501, 447882868, 2892677553, 3287394621, 2397328790, 2248463212,
1418526562, 2117014926, 3686766031, 298649829, 584205839, 3627557585, 2998315853,
2977920493, 726632938, 3587672184, 2031497493, 3536637527, 2147351398, 2994151365,
2357491055, 2685427052, 561736037, 249434731, 37851003, 2139420207, 1456949077,
3499596051, 2387808327, 698459036, 2829626440, 1153227452, 2967364067, 1308820861,
3023499589, 3279604314, 1351494432, 889784871, 236547645, 2007227680, 595443432,
1146281314, 3645152419, 3684480237, 1893493610, 3759196246, 1654652555, 1570985606,
3168763126, 1011656140, 443293510, 4075348841, 3769289235, 3178746711, 2447901158,
1462169783, 2059860955, 3176730687, 4250518815, 2494049638, 2842999845, 2660773548,
2429754290, 2910792523, 447755453, 1292065721, 1364296417, 531674748, 2193540777,
2412916570, 28609683, 2221611024, 3779881643, 4195316838, 743899040, 4213767553,
27880778, 1574053906, 1155505137, 439874260, 3750284675, 3525838570, 1095901379,
578703301, 3049020885, 3076480478, 600357557, 485719043, 2996666070, 969220829,
382916967, 4127194422, 1105131550, 1274911215, 804142925, 1973587943, 3032041047,
3584540133, 3351136224, 3543725084, 2962955598, 4293881521, 2425133896, 660514410,
3361169054, 77763049, 4229878743, 4011932021, 1090195601, 275885704, 3640421637,
1393243181, 1181392749, 3389311176, 2310097427, 289908933, 1711535789, 4033213111,
393665786, 923868932, 4018570793, 760848544, 674950332, 3344550397, 4011950991,
190003021, 4198189972, 3933037427, 3414307787, 3621605663, 3363592942, 2828152179,
644352484, 2918972032, 3175404448, 1785883817, 3697552954, 733843149, 286590854,
1214528285, 4166016418, 471561591, 2415332960, 1189766994, 1211081173, 4272651438,
3658504023, 755193424, 1817559547, 3945505192, 2450391056, 608673849, 1759503207,
340654448, 4134788276, 716854876, 1927628933, 3770411883, 3272236481, 3570235672,
326127009, 243730071, 1195661416, 3081806246, 3497515351, 2099772515, 1455307780,
1228408049, 4104831308, 1973834358, 4080297784, 578026510, 1512759928, 1470813128,
2584189047, 2637446524, 1698422615, 1284857912, 486923383, 174367540, 3702801188,
1161365394, 2737086689, 4265331868, 2412069202, 1870108327, 701659394, 2415165383,
1604722515, 2870993251, 471129547, 1280015857, 2050493217, 274565042, 2441183839,
3443859668, 2340505028, 1660404263, 2752768160, 560703857, 2104329624, 3452739653,
1013253476, 721912154, 1823929621, 3194765430, 1314309520, 4145569405, 1487647842,
1711679024, 1867628450, 2953439882, 1443642820, 2877245620, 2468137212, 3585016849,
2470055841, 2779688530, 3723417454, 2154058910, 1467213764, 3245268497, 4158596454,
4019385724, 2344037496, 1740779840, 4048853262, 1322676367, 2118663058, 2422287837,
2128664579, 2216474287, 1392815988, 747608508, 3828366939, 1008849042, 2597739640,
1600350391, 1209606111, 1982580858, 1492943335, 3554519928, 154739547, 1939048949,
],
-1,
);
test(
&[
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967168,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294950912,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
7,
0,
0,
0,
0,
3758096384,
524287,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2147483648,
16777215,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4290772992,
],
&[
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
32767,
0,
0,
0,
0,
0,
0,
4294967232,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
31,
0,
0,
0,
0,
0,
3758096384,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
511,
0,
0,
0,
0,
0,
0,
4294934528,
u32::MAX,
u32::MAX,
536870911,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4286578688,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
511,
0,
0,
0,
3758096384,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
2047,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4292870144,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
65535,
4227858432,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
15,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
],
-1,
);
test(
&[
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
262143,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4026531840,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
16383,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
3758096384,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
131071,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4293918720,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
],
&[
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
511,
0,
0,
0,
0,
0,
0,
2147483648,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
16777215,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4160749568,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
7,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967264,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
134217727,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
3758096384,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
536870911,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294836224,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
15,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
],
1,
);
test(
&[
1077171533, 3384534038, 3509377481, 3012981171, 2169372009, 3568066367, 510541737,
360351115, 1116770051, 2058732872, 3226198045, 1078176389, 2950624729, 812262025,
1430083408, 61306667, 64349919, 2388720201, 2804807299, 3487065571, 1162686670,
2184575935, 1234374819, 3462973209, 2204618738, 1955732567, 4274764191, 487910035,
2794693464, 1455130957, 2647605728, 4211289912, 3386405281, 117329687, 3432428417,
1300225461, 3461206919, 449524200, 904979455, 3971171435, 441380375, 1283836003,
2682594354, 1152961793, 1318795928, 308922730, 628004645, 1003117196, 1035594263,
3028460626, 3737759554, 3080878651, 2013071269, 157811103, 3209212678, 1794098871,
1571763958, 4118994167, 3323265833, 2779923965, 1781531454, 3074442432, 1330835008,
231050954, 1972822306, 3779389322, 2550908177, 1122947161, 2607600449, 2966179614,
1165225297, 4222222976, 1020266087, 1019514006, 53769477, 62821411, 3078440286,
2087323177, 4209236301, 146146381, 453393163, 4244430148, 624415024, 2096395426,
1915435196, 3779399544, 3641826296, 4157323023, 4049792386, 1892149154, 2185863226,
1046224168, 3568999985, 982204298, 154455361, 2605934809, 2605177974, 1652215061,
3058430834, 1573346022, 3979000833, 1424146496, 758475042, 3880559465, 3331749655,
4009275982, 309023272, 343958017, 2544085697, 1960862631, 1082361995, 534185037,
331011064, 3662295811, 3280920837, 2366184597, 1029851460, 1149922348, 3242309342,
3498011365, 1869617138, 2033933372, 2449772239, 1769059102, 552671522, 2541136194,
1837261562, 3331388737, 3882095076, 2111080116, 3488393361, 3110154197, 2503543094,
276095820, 109038743, 3401659741, 2955647843, 3730124703, 4288579615, 2840357519,
433563482, 3742367408, 2287152115, 3054337338, 2305325930, 1838329967, 1117989732,
2731369203, 427022429, 1959348870, 107371881, 1378273431, 3969746745, 137314119,
3494302009, 2316521941, 1304670415, 2017956904, 3960566359, 3950960171, 2483760563,
3248620299, 1282201932, 2666453601, 290925463, 1315172510, 2244058356, 83064665,
2794575253, 2751020494, 86251099, 1497864163, 1309606664, 918139255, 2382232313,
3431694285, 4197334044, 3779739436, 2597050321, 4053750034, 1347898240, 2068381165,
530540195, 777294114, 1563424547, 714733079, 251090961, 1222614986, 409927269,
2552943554, 3813553790, 2619995688, 2754487462, 1001623689, 4043538191, 780110724,
2756539090, 2640687797, 2974350673, 1702213372, 2898669867, 232176052, 2414666354,
300281312, 3252747308, 2375533144, 3579260801, 3856594937, 226065085, 2855017957,
4106625762, 4251800319, 271717704, 796181594, 2015816818, 572129733, 1578027849,
208352494, 3329313861, 3272451839, 1390383564, 3754291474, 1022210892, 3402379185,
1055267474, 2105880379, 1377373336, 2125916506, 3713096588, 3227913500, 593660170,
3662162553, 948899397, 3959019656, 743736078, 561608271, 4154259253, 753202703,
3057879152, 4093431092, 2849520862, 1298183896, 1072767461, 3844624206, 1553109174,
2211737614, 2944064724, 1134344972, 2846368205, 2535247938, 1454739286, 1408186915,
3022639671, 2985835925, 1242350664, 856614531, 3277904750, 2435844371, 2288413570,
1941580081, 2330069009, 3763753263, 1617186357, 3858822820, 3899619764, 957776791,
2415934649, 1903499570, 362345092, 3162421697, 857308796, 2166848441, 2794392063,
2916482641, 547554093, 393697940, 319583576, 3206427070, 3502792667, 3979846702,
3580352012, 3854879140, 3646613450, 4113031775, 856333171, 1029998771, 2090645466,
3125086584, 2494710984, 3249027001, 3828101842, 4278721100, 2901896440, 3549366611,
2066085974, 3815811960, 2980213693, 2418009668, 4168963107, 1522903282, 3921187989,
209293309, 1026651789, 3652402308, 1723212287, 3005358245, 3972955479, 3432513818,
1135457591, 2609451544, 1728509125, 1610815908, 1281322374, 2308282400, 1650462965,
785788526, 3039230497, 1454810597, 2847801652, 868324593, 2811238675, 1592440137,
2837082164, 2293886194, 108023352, 1338057151, 867454780, 660204887, 2727424012,
3251699301, 2307270502, 3508727390, 444210859, 4112897129, 1692014843, 232384981,
3746950478, 2035293041, 832494472, 4167968781, 2088468820, 1082123254, 2004377194,
739887690, 3903970376, 3917684808, 2220241302, 1623595193, 3168893289, 1380144222,
3245294302, 1942246969, 1017235276, 1075796476, 1420638313, 2370978268, 3571300703,
2818383559, 3979048442, 4070073076, 3639658932, 2458302928, 1936855091, 1097653713,
2517446959, 395058431, 2490534065, 3621579656, 537422087, 820775047, 1621745064,
4147607605, 773085439, 150346009, 3309770346, 623052976, 223120997, 1047915001,
2440220896, 2701090680, 682463717, 626719149, 2752394251, 2245504316, 3599570937,
1008202886, 3061625147, 3833145985, 2287104975, 3419855448, 542949621, 2260871982,
3411141468, 1089194931, 3865896761, 1906114014, 3523746087, 3034843700, 3980408914,
1779312499, 2670385907, 3943945115, 3040560985, 968208310,
],
&[
1077171533, 3384534038, 3509377481, 3012981171, 2169372009, 3568066367, 510541737,
360351115, 1116770051, 2058732872, 3226198045, 1078176389, 2950624729, 812262025,
1430083408, 61306667, 64349919, 2388720201, 2804807299, 3487065571, 1162686670,
2184575935, 1234374819, 3462973209, 2204618738, 1955732567, 4274764191, 487910035,
2794693464, 1455130957, 2647605728, 4211289912, 3386405281, 117329687, 3432428417,
1300225461, 3461206919, 449524200, 904979455, 3971171435, 441380375, 1283836003,
2682594354, 1152961793, 1318795928, 308922730, 628004645, 1003117196, 1035594263,
3028460626, 3737759554, 3080878651, 2013071269, 157811103, 3209212678, 1794098871,
1571763958, 4118994167, 3323265833, 2779923965, 1781531454, 3074442432, 1330835008,
231050954, 1972822306, 3779389322, 2550908177, 1122947161, 2607600449, 2966179614,
1165225297, 4222222976, 1020266087, 1019514006, 53769477, 62821411, 3078440286,
2087323177, 4209236301, 146146381, 453393163, 4244430148, 624415024, 2096395426,
1915435196, 3779399544, 3641826296, 4157323023, 4049792386, 1892149154, 2185863226,
1046224168, 3568999985, 982204298, 154455361, 2605934809, 2605177974, 1652215061,
3058430834, 1573346022, 3979000833, 1424146496, 758475042, 3880559465, 3331749655,
4009275982, 309023272, 343958017, 2544085697, 1960862631, 1082361995, 534185037,
331011064, 3662295811, 3280920837, 2366184597, 1029851460, 1149922348, 3242309342,
3498011365, 1869617138, 2033933372, 2449772239, 1769059102, 552671522, 2541136194,
1837261562, 3331388737, 3882095076, 2111080116, 3488393361, 3110154197, 2503543094,
276095820, 109038743, 3401659741, 2955647843, 3730124703, 4288579615, 2840357519,
433563482, 3742367408, 2287152115, 3054337338, 2305325930, 1838329967, 1117989732,
2731369203, 427022429, 1959348870, 107371881, 1378273431, 3969746745, 137314119,
3494302009, 2316521941, 1304670415, 2017956904, 3960566359, 3950960171, 2483760563,
3248620299, 1282201932, 2666453601, 290925463, 1315172510, 2244058356, 83064665,
2794575253, 2751020494, 86251099, 1497864163, 1309606664, 918139255, 2382232313,
3431694285, 4197334044, 3779739436, 2597050321, 4053750034, 1347898240, 2068381165,
530540195, 777294114, 1563424547, 714733079, 251090961, 1222614986, 409927269,
2552943554, 3813553790, 2619995688, 2754487462, 1001623689, 4043538191, 780110724,
2756539090, 2640687797, 2974350673, 1702213372, 2898669867, 232176052, 2414666354,
300281312, 3252747308, 2375533144, 3579260801, 3856594937, 226065085, 2855017957,
4106625762, 4251800319, 271717704, 796181594, 2015816818, 572129733, 1578027849,
208352494, 3329313861, 3272451839, 1390383564, 3754291474, 1022210892, 3402379185,
1055267474, 2105880379, 1377373336, 2125916506, 3713096588, 3227913500, 593660170,
3662162553, 948899397, 3959019656, 743736078, 561608271, 4154259253, 753202703,
3057879152, 4093431092, 2849520862, 1298183896, 1072767461, 3844624206, 1553109174,
2211737614, 2944064724, 1134344972, 2846368205, 2535247938, 1454739286, 1408186915,
3022639671, 2985835925, 1242350664, 856614531, 3277904750, 2435844371, 2288413570,
1941580081, 2330069009, 3763753263, 1617186357, 3858822820, 3899619764, 957776791,
2415934649, 1903499570, 362345092, 3162421697, 857308796, 2166848441, 2794392063,
2916482641, 547554093, 393697940, 319583576, 3206427070, 3502792667, 3979846702,
3580352012, 3854879140, 3646613450, 4113031775, 856333171, 1029998771, 2090645466,
3125086584, 2494710984, 3249027001, 3828101842, 4278721100, 2901896440, 3549366611,
2066085974, 3815811960, 2980213693, 2418009668, 4168963107, 1522903282, 3921187989,
209293309, 1026651789, 3652402308, 1723212287, 3005358245, 3972955479, 3432513818,
1135457591, 2609451544, 1728509125, 1610815908, 1281322374, 2308282400, 1650462965,
785788526, 3039230497, 1454810597, 2847801652, 868324593, 2811238675, 1592440137,
2837082164, 2293886194, 108023352, 1338057151, 867454780, 660204887, 2727424012,
3251699301, 2307270502, 3508727390, 444210859, 4112897129, 1692014843, 232384981,
3746950478, 2035293041, 832494472, 4167968781, 2088468820, 1082123254, 2004377194,
739887690, 3903970376, 3917684808, 2220241302, 1623595193, 3168893289, 1380144222,
3245294302, 1942246969, 1017235276, 1075796476, 1420638313, 2370978268, 3571300703,
2818383559, 3979048442, 4070073076, 3639658932, 2458302928, 1936855091, 1097653713,
2517446959, 395058431, 2490534065, 3621579656, 537422087, 820775047, 1621745064,
4147607605, 773085439, 150346009, 3309770346, 623052976, 223120997, 1047915001,
2440220896, 2701090680, 682463717, 626719149, 2752394251, 2245504316, 3599570937,
1008202886, 3061625147, 3833145985, 2287104975, 3419855448, 542949621, 2260871982,
3411141468, 1089194931, 3865896761, 1906114014, 3523746087, 3034843700, 3980408914,
1779312499, 2670385907, 3943945115, 3040560985, 968208310,
],
0,
);
test(
&[
2527776570, 1096068921, 3262306218, 1320735475, 3585033863, 837181718, 1434028202,
101347753, 1225665622, 67225439, 876392417, 2005928391, 1055641927, 2192872866,
2819789958, 730215470, 1621800044, 4036225587, 3556548105, 3110943208, 3185668368,
2027089067, 2101840218, 4225448827, 3021189927, 4280012260, 3622060673, 2596479319,
2588713825, 1028636336, 3005767087, 1249021277, 4164898722, 731420324, 1545357905,
1990024360, 2640852447, 2424127910, 1870854337, 1406415699, 2196092126, 1310967564,
232318981, 3146607976, 4083502397, 22174679, 3737886384, 3144967018, 4263470608,
3780127714, 2165861131, 3336828897, 1694667359, 1492938371, 494778850, 3046154974,
1157896728, 3074135421, 2504833163, 810655235, 1557262964, 1363420755, 2702433995,
1177464584, 3371204921, 3586238385, 281106173, 1653503734, 2385994192, 3794586631,
3194300174, 847482886, 2910519739, 3968032513, 1772081491, 2782405946, 4234346611,
3594663949, 2600834058, 1201913439, 3836544822, 2596924324, 3356614882, 1073086697,
4071118647, 1627306041, 25361421, 5025, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
],
&[
5737393, 656355346, 2428436877, 1659347327, 1816624877, 3040364388, 1159326770,
4206559661, 3092296489, 1558251555, 1049236200, 2222235583, 2014235172, 3291004209,
934339935, 985867991, 762407537, 1409401405, 778491764, 3564656357, 128109175,
2460849082, 1890568470, 461692287, 817897242, 602238225, 920048131, 3418406322,
708192111, 2567463295, 1875671904, 1148800469, 3212120696, 566830399, 1427401847,
3369501422, 3485886037, 2817269664, 2227802377, 4283410186, 2703903094, 936664805,
4157101885, 2263955722, 2647106937, 537917125, 4056960194, 3912645532, 354245311,
2717804064, 1109582468, 2727640815, 425052729, 2611473321, 3879075705, 716899167,
1914192905, 2601501681, 462694240, 205229129, 1093878128, 410346932, 3439980661,
667954709, 1052656728, 2148601811, 2379731442, 2268999665, 3706142073, 1456579358,
3757504240, 463695214, 1436957313, 2049267296, 3303570927, 1864647396, 900688508,
1835551150, 71395285, 1425899737, 2287259914, 962161837, 2938663406, 2857261272,
1146595809, 3764487743, 3300056528, 3137301789, 250445987, 1997329543, 192312160,
3417776853, 3623584574, 2403647678, 3849791382, 3065151486, 2112108309, 2184865682,
2147711161, 3337243558, 2646696137, 3744234210, 3469704297, 804280152, 2812030004,
283967646, 1530700123, 2959520978, 133999661, 1311943460, 2409420442, 1378063817,
1306691126, 2795816917, 175853898, 3436153597, 4094879999, 4061387058, 3142348235,
3450122749, 997635528, 2383423341, 946776870, 1390313886, 4272495253, 1329111605,
1783381058, 1235280956, 878145167, 1050060880, 4215806346, 986268144, 2398596766,
1847782969, 2662963332, 320753973, 961489657, 643166461, 3665561600, 903526756,
861869280, 1582519883, 1724972430, 3647434888, 922278554, 1608919692, 3498480811,
606385525, 1264439673, 1258996822, 3155308373, 1047873974, 2173644429, 1417008977,
935021011, 722697374, 3318510778, 638992840, 1692733318, 1533146701, 2599254955,
3256732986, 11478574, 3245879834, 3651129160, 890914331, 1936401914, 4269069338,
652796490, 1855438614, 3711917465, 2231167869, 965528216, 4083742438, 3888862032,
4027832595, 3194731005, 3855267812, 1331497794, 1036129210, 2454849236, 3936763814,
2166230922, 2221233340, 3494633119, 2135677604, 1957161469, 3441858755, 3165789630,
3502273733, 3935502624, 935473926, 951630970, 3241427305, 3626833422, 3344353486,
384196385, 2893969144, 371257580, 1895300995, 1538534547, 4247925735, 3906194642,
3278920998, 190467029, 660834078, 3047471694, 3139110501, 2945327231, 2791821139,
3787430397, 11897902, 3071804998, 2906353083, 3986347125, 728226352, 1721418756,
3790033644, 2543845828, 4201817595, 1241190909, 2172638407, 3176874190, 212681671,
2217059787, 2568436099, 4160058240, 1550824349, 1589798596, 2384281069, 4106120578,
1772814852, 2711184704, 1753902606, 3147375646, 3197706153, 4069187110, 2497336677,
682542752, 3631288002, 1821492432, 4111201809, 3496083848, 488832033, 1487521654,
1028323258, 2626975117, 3820273648, 4203958355, 1957204165, 692251647, 751713885,
2869803205, 699099042, 287040513, 1256261134, 1435317843, 2516495821, 2172617698,
2350001365, 3127743304, 4210222956, 2394254147, 1395276753, 2466938438, 1054538356,
145981627, 152373092, 2285902580, 534742531, 2919481209, 1870713895, 800843175,
3498230341, 29966677, 1374519390, 1746138239, 90290568, 2136928464, 1012080534,
4220785618, 2331149605, 3177894074, 4194250977, 1793677512, 1812254290, 755277024,
1050843937, 1441079766, 4177809358, 2569374720, 2516736232, 1486921399, 666656868,
1100619139, 2587149122, 2221024508, 2951375366, 2349454937, 4266896936, 4091705443,
4244036995, 3327195836, 2611529411, 538404573, 3970374943, 3102287318, 1164998997,
521166464, 3125925988, 360672675, 3568959356, 1328059403, 2778221822, 347086039,
3797350591, 3600929164, 849738110, 3879666101, 2751748132, 3317854867, 2059575942,
3146620321, 1367551383, 2518113922, 2136751883, 4171468116, 4267631229, 3031791643,
2334887552, 2773212213, 480854415, 482867572, 8189,
],
1,
);
test(
&[
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
1023,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967280,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
8191,
0,
0,
0,
0,
0,
0,
0,
0,
4294967288,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
8388607,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4278190080,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
16383,
0,
0,
0,
4292870144,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
],
&[
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
134217727,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294965248,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
511,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4290772992,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
262143,
0,
0,
4292870144,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
524287,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967294,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4278190080,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
16777215,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967292,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
65535,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
4294967168,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
u32::MAX,
],
0,
);
test(
&[
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0,
],
&[
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1,
],
1,
);
}
}
#[test]
fn test_legendre_symbol() {
fn test(u: &str, v: &str, s: i8) {
let a = Natural::from_str(u).unwrap();
let n = Natural::from_str(v).unwrap();
assert_eq!(a.clone().legendre_symbol(n.clone()), s);
assert_eq!(a.clone().legendre_symbol(&n), s);
assert_eq!((&a).legendre_symbol(n.clone()), s);
assert_eq!((&a).legendre_symbol(&n), s);
assert_eq!(a.clone().jacobi_symbol(n.clone()), s);
assert_eq!(a.clone().jacobi_symbol(&n), s);
assert_eq!((&a).jacobi_symbol(n.clone()), s);
assert_eq!((&a).jacobi_symbol(&n), s);
assert_eq!(a.clone().kronecker_symbol(n.clone()), s);
assert_eq!(a.clone().kronecker_symbol(&n), s);
assert_eq!((&a).kronecker_symbol(n.clone()), s);
assert_eq!((&a).kronecker_symbol(&n), s);
assert_eq!(jacobi_symbol_simple(a, n), s);
assert_eq!(
rug::Integer::from_str(u)
.unwrap()
.legendre(&rug::Integer::from_str(v).unwrap()),
i32::from(s)
);
}
test("0", "3", 0);
test("1", "3", 1);
test("2", "3", -1);
test("0", "5", 0);
test("1", "5", 1);
test("2", "5", -1);
test("3", "5", -1);
test("4", "5", 1);
test("0", "7", 0);
test("1", "7", 1);
test("2", "7", 1);
test("3", "7", -1);
test("4", "7", 1);
test("5", "7", -1);
test("6", "7", -1);
test("7", "7", 0);
test("8", "7", 1);
test("9", "7", 1);
test("10", "7", -1);
test("11", "7", 1);
test("12", "7", -1);
test("13", "7", -1);
test("1001", "9907", -1);
test("10908", "9907", -1);
}
#[test]
fn legendre_symbol_fail() {
assert_panic!(Natural::ONE.legendre_symbol(Natural::TWO));
assert_panic!(Natural::ONE.legendre_symbol(&Natural::TWO));
assert_panic!((&Natural::ONE).legendre_symbol(Natural::TWO));
assert_panic!((&Natural::ONE).legendre_symbol(&Natural::TWO));
}
#[test]
fn test_jacobi_symbol() {
fn test(u: &str, v: &str, s: i8) {
let a = Natural::from_str(u).unwrap();
let n = Natural::from_str(v).unwrap();
assert_eq!(a.clone().jacobi_symbol(n.clone()), s);
assert_eq!(a.clone().jacobi_symbol(&n), s);
assert_eq!((&a).jacobi_symbol(n.clone()), s);
assert_eq!((&a).jacobi_symbol(&n), s);
assert_eq!(a.clone().kronecker_symbol(n.clone()), s);
assert_eq!(a.clone().kronecker_symbol(&n), s);
assert_eq!((&a).kronecker_symbol(n.clone()), s);
assert_eq!((&a).kronecker_symbol(&n), s);
assert_eq!(jacobi_symbol_simple(a, n), s);
assert_eq!(
rug::Integer::from_str(u)
.unwrap()
.jacobi(&rug::Integer::from_str(v).unwrap()),
i32::from(s)
);
}
test("0", "1", 1);
test("0", "9", 0);
test("1", "9", 1);
test("2", "9", 1);
test("3", "9", 0);
test("4", "9", 1);
test("5", "9", 1);
test("6", "9", 0);
test("7", "9", 1);
test("8", "9", 1);
test("9", "9", 0);
test("10", "9", 1);
test("11", "9", 1);
test("12", "9", 0);
test("13", "9", 1);
test("14", "9", 1);
test("15", "9", 0);
test("16", "9", 1);
test("17", "9", 1);
}
#[test]
fn jacobi_symbol_fail() {
assert_panic!(Natural::ONE.jacobi_symbol(Natural::TWO));
assert_panic!(Natural::ONE.jacobi_symbol(&Natural::TWO));
assert_panic!((&Natural::ONE).jacobi_symbol(Natural::TWO));
assert_panic!((&Natural::ONE).jacobi_symbol(&Natural::TWO));
}
#[test]
fn test_kronecker_symbol() {
fn test(u: &str, v: &str, s: i8) {
let a = Natural::from_str(u).unwrap();
let n = Natural::from_str(v).unwrap();
assert_eq!(a.clone().kronecker_symbol(n.clone()), s);
assert_eq!(a.clone().kronecker_symbol(&n), s);
assert_eq!((&a).kronecker_symbol(n.clone()), s);
assert_eq!((&a).kronecker_symbol(&n), s);
assert_eq!(
rug::Integer::from_str(u)
.unwrap()
.kronecker(&rug::Integer::from_str(v).unwrap()),
i32::from(s)
);
}
test("0", "2", 0);
test("1", "2", 1);
test("2", "2", 0);
test("3", "2", -1);
test("4", "2", 0);
test("5", "2", -1);
test("6", "2", 0);
test("7", "2", 1);
test("0", "4", 0);
test("1", "4", 1);
test("2", "4", 0);
test("3", "4", 1);
test("0", "6", 0);
test("1", "6", 1);
test("2", "6", 0);
test("3", "6", 0);
test("4", "6", 0);
test("5", "6", 1);
test("6", "6", 0);
test("7", "6", 1);
test("8", "6", 0);
test("9", "6", 0);
test("10", "6", 0);
test("11", "6", 1);
test("12", "6", 0);
test("13", "6", -1);
test("14", "6", 0);
test("15", "6", 0);
test("16", "6", 0);
test("17", "6", -1);
test("18", "6", 0);
test("19", "6", -1);
test("20", "6", 0);
test("21", "6", 0);
test("22", "6", 0);
test("23", "6", -1);
test("1001", "9908", -1);
test("10909", "9908", -1);
}
#[test]
fn limbs_jacobi_symbol_same_length_properties() {
let mut config = GenConfig::new();
config.insert("mean_length_n", 256);
config.insert("mean_stripe_n", 32 << Limb::LOG_WIDTH);
unsigned_vec_pair_gen_var_32().test_properties_with_config(&config, |(mut xs, mut ys)| {
let x = Natural::from_limbs_asc(&xs);
let y = Natural::from_limbs_asc(&ys);
let s = (&x).jacobi_symbol(&y);
assert_eq!(jacobi_symbol_simple(x, y), s);
let bits = limbs_jacobi_symbol_init(xs[0], ys[0], 0);
assert_eq!(limbs_jacobi_symbol_same_length(&mut xs, &mut ys, bits), s);
});
}
#[test]
fn jacobi_symbol_properties() {
natural_pair_gen_var_12().test_properties(|(a, n)| {
let s = (&a).jacobi_symbol(&n);
assert_eq!((&a).jacobi_symbol(n.clone()), s);
assert_eq!(a.clone().jacobi_symbol(&n), s);
assert_eq!(a.clone().jacobi_symbol(n.clone()), s);
assert_eq!((&a).legendre_symbol(&n), s);
assert_eq!((&a).legendre_symbol(n.clone()), s);
assert_eq!(a.clone().legendre_symbol(&n), s);
assert_eq!(a.clone().legendre_symbol(n.clone()), s);
assert_eq!((&a).kronecker_symbol(&n), s);
assert_eq!((&a).kronecker_symbol(n.clone()), s);
assert_eq!(a.clone().kronecker_symbol(&n), s);
assert_eq!(a.clone().kronecker_symbol(n.clone()), s);
assert_eq!(jacobi_symbol_simple(a.clone(), n.clone()), s);
assert_eq!(
rug::Integer::from(&a).jacobi(&rug::Integer::from(&n)),
i32::from(s)
);
assert!(s.le_abs(&1i8));
assert_eq!((&a + &n).jacobi_symbol(&n), s);
if a >= n {
assert_eq!((&a - &n).jacobi_symbol(&n), s);
}
assert_eq!(s != 0, (&a).coprime_with(&n));
let n_mod_8: u8 = (&(&n).mod_power_of_2(3)).wrapping_into();
assert_eq!(
(a << 1u32).jacobi_symbol(n),
if n_mod_8 == 1 || n_mod_8 == 7 { s } else { -s }
);
});
natural_pair_gen_var_13().test_properties(|(m, n)| {
let n_mod_4: u8 = (&(&n).mod_power_of_2(2)).wrapping_into();
let m_mod_4: u8 = (&(&m).mod_power_of_2(2)).wrapping_into();
assert_eq!(
(&m).jacobi_symbol(&n) * n.jacobi_symbol(m),
if n_mod_4 == 1 || m_mod_4 == 1 { 1 } else { -1 }
);
});
natural_triple_gen_var_8().test_properties(|(a, b, n)| {
assert_eq!(
(&a * &b).jacobi_symbol(&n),
a.jacobi_symbol(&n) * b.jacobi_symbol(n)
);
});
natural_triple_gen_var_9().test_properties(|(a, m, n)| {
assert_eq!(
(&a).jacobi_symbol(&m * &n),
(&a).jacobi_symbol(m) * a.jacobi_symbol(n)
);
});
natural_gen_var_8().test_properties(|n| {
if n != 1u32 {
assert_eq!(Natural::ZERO.jacobi_symbol(&n), 0);
assert_eq!((&n).jacobi_symbol(&n), 0);
}
assert_eq!(Natural::ONE.jacobi_symbol(&n), 1);
assert_eq!((&n).jacobi_symbol(Natural::ONE), 1);
let n_mod_4: u8 = (&(&n).mod_power_of_2(2)).wrapping_into();
assert_eq!(
(&n - Natural::ONE).jacobi_symbol(&n),
if n_mod_4 == 1 { 1 } else { -1 }
);
let n_mod_8: u8 = (&(&n).mod_power_of_2(3)).wrapping_into();
assert_eq!(
Natural::TWO.jacobi_symbol(&n),
if n_mod_8 == 1 || n_mod_8 == 7 { 1 } else { -1 }
);
});
unsigned_pair_gen_var_40::<Limb>().test_properties(|(x, y)| {
assert_eq!(
Natural::from(x).jacobi_symbol(Natural::from(y)),
x.jacobi_symbol(y)
);
});
}
fn kronecker_symbol_properties_helper(a: Natural, n: Natural) {
let s = (&a).kronecker_symbol(&n);
assert_eq!((&a).kronecker_symbol(n.clone()), s);
assert_eq!(a.clone().kronecker_symbol(&n), s);
assert_eq!(a.clone().kronecker_symbol(n.clone()), s);
assert_eq!(
rug::Integer::from(&a).kronecker(&rug::Integer::from(&n)),
i32::from(s)
);
assert!(s.le_abs(&1i8));
assert_eq!(s != 0, (&a).coprime_with(&n));
let n_mod_4: u8 = (&(&n).mod_power_of_2(2)).wrapping_into();
if n_mod_4 == 2 {
let four_n = &n << 2u32;
assert_eq!((&a + &four_n).kronecker_symbol(&n), s);
if a >= four_n {
assert_eq!((&a - four_n).kronecker_symbol(&n), s);
}
} else {
assert_eq!((&a + &n).kronecker_symbol(&n), s);
if a >= n {
assert_eq!((&a - &n).kronecker_symbol(&n), s);
}
}
let a_mod_4: u8 = (&(&a).mod_power_of_2(2)).wrapping_into();
if a != 0u32 && a_mod_4 != 3 {
if a_mod_4 == 2 {
let four_a = &a << 2u32;
assert_eq!((&a).kronecker_symbol(&n + &four_a), s);
if n >= four_a {
assert_eq!((&a).kronecker_symbol(&n - four_a), s);
}
} else {
assert_eq!((&a).kronecker_symbol(&n + &a), s);
if n >= a {
let diff = n - &a;
assert_eq!((a).kronecker_symbol(diff), s);
}
}
}
}
#[test]
fn kronecker_symbol_properties() {
let mut config = GenConfig::new();
config.insert("mean_bits_n", 2048);
config.insert("mean_stripe_n", 512 << Limb::LOG_WIDTH);
natural_pair_gen().test_properties_with_config(&config, |(x, y)| {
kronecker_symbol_properties_helper(x, y);
});
natural_pair_gen_var_4().test_properties_with_config(&config, |(x, y)| {
kronecker_symbol_properties_helper(x, y);
});
natural_triple_gen().test_properties(|(x, y, z)| {
assert_eq!(
(&x * &y).kronecker_symbol(&z),
(&x).kronecker_symbol(&z) * (&y).kronecker_symbol(&z)
);
assert_eq!(
(&x).kronecker_symbol(&y * &z),
(&x).kronecker_symbol(y) * x.kronecker_symbol(z)
);
});
natural_pair_gen_var_14().test_properties(|(m, n)| {
let n_odd = if n == 0u32 {
Natural::ONE
} else {
&n >> n.trailing_zeros().unwrap()
};
let m_odd = if m == 0u32 {
Natural::ONE
} else {
&m >> m.trailing_zeros().unwrap()
};
let n_odd_mod_4: u8 = (&n_odd.mod_power_of_2(2)).wrapping_into();
let m_odd_mod_4: u8 = (&m_odd.mod_power_of_2(2)).wrapping_into();
let p = if n_odd_mod_4 == 1 || m_odd_mod_4 == 1 {
1
} else {
-1
};
assert_eq!((&m).kronecker_symbol(&n) * n.kronecker_symbol(m), p);
});
natural_gen().test_properties(|n| {
if n != 1u32 {
assert_eq!(Natural::ZERO.kronecker_symbol(&n), 0);
assert_eq!((&n).kronecker_symbol(&n), 0);
}
assert_eq!(Natural::ONE.kronecker_symbol(&n), 1);
assert_eq!(n.kronecker_symbol(Natural::ONE), 1);
});
unsigned_pair_gen_var_27::<Limb>().test_properties(|(x, y)| {
assert_eq!(
Natural::from(x).kronecker_symbol(Natural::from(y)),
x.kronecker_symbol(y)
);
});
}