dconvstr.c

/*
 *  Bijective, heapless and bignumless conversion of IEEE 754 double to string and vice versa
 *  http://www.gurucoding.com/en/dconvstr/
 *
 *  Copyright (c) 2014 Mikhail Kupchik <Mikhail.Kupchik@prime-expert.com>
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without modification, are permitted 
 *  provided that the following conditions are met:
 *
 *  1. Redistributions of source code must retain the above copyright notice, this list of conditions
 *     and the following disclaimer.
 *
 *  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions
 *     and the following disclaimer in the documentation and/or other materials provided with the 
 *     distribution.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 
 *  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 
 *  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 *  IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 *  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include "dconvstr.h"

#include <string.h>
#ifndef _MSC_VER
#  include <stdint.h>
#else
#  include <intrin.h>
   typedef unsigned char     uint8_t;
   typedef __int32           int32_t;
   typedef unsigned __int32  uint32_t;
   typedef unsigned __int64  uint64_t;
#endif


//=====================================================================================================
//
// TYPES AND CONSTANTS
//

// 10^18 constant
#define POW10_18  ((1000ULL * 1000ULL * 1000ULL) * (1000ULL * 1000ULL * 1000ULL))

// Double-to-string parser states
enum  parser_state { S0, S1, S2, S3, S4, S5, S6, S7 };

// Table: powers of ten in binary representation.
// 10^decimal_exponent ~= binary_mantissa * 2^binary_exponent.
// 2^63 < binary_mantissa < 2^64, mantissa has been rounded to nearest integer.
// Covers entire range of IEEE 754 double, including denormals, plus small spare.
struct  power_of_ten
{
    int32_t   decimal_exponent;
    int32_t   binary_exponent;
    uint64_t  binary_mantissa;
};
static const struct power_of_ten  powers_of_ten_[] = {
    { -344, -1206,  11019826852086880396ULL },    { -343, -1203,  13774783565108600494ULL },
    { -342, -1200,  17218479456385750618ULL },    { -341, -1196,  10761549660241094136ULL },
    { -340, -1193,  13451937075301367670ULL },    { -339, -1190,  16814921344126709588ULL },
    { -338, -1186,  10509325840079193492ULL },    { -337, -1183,  13136657300098991866ULL },
    { -336, -1180,  16420821625123739832ULL },    { -335, -1176,  10263013515702337395ULL },
    { -334, -1173,  12828766894627921744ULL },    { -333, -1170,  16035958618284902180ULL },
    { -332, -1166,  10022474136428063862ULL },    { -331, -1163,  12528092670535079828ULL },
    { -330, -1160,  15660115838168849785ULL },    { -329, -1156,   9787572398855531116ULL },
    { -328, -1153,  12234465498569413894ULL },    { -327, -1150,  15293081873211767368ULL },
    { -326, -1146,   9558176170757354605ULL },    { -325, -1143,  11947720213446693256ULL },
    { -324, -1140,  14934650266808366570ULL },    { -323, -1136,   9334156416755229106ULL },
    { -322, -1133,  11667695520944036383ULL },    { -321, -1130,  14584619401180045479ULL },
    { -320, -1127,  18230774251475056849ULL },    { -319, -1123,  11394233907171910530ULL },
    { -318, -1120,  14242792383964888163ULL },    { -317, -1117,  17803490479956110204ULL },
    { -316, -1113,  11127181549972568877ULL },    { -315, -1110,  13908976937465711097ULL },
    { -314, -1107,  17386221171832138871ULL },    { -313, -1103,  10866388232395086794ULL },
    { -312, -1100,  13582985290493858493ULL },    { -311, -1097,  16978731613117323116ULL },
    { -310, -1093,  10611707258198326947ULL },    { -309, -1090,  13264634072747908684ULL },
    { -308, -1087,  16580792590934885855ULL },    { -307, -1083,  10362995369334303660ULL },
    { -306, -1080,  12953744211667879575ULL },    { -305, -1077,  16192180264584849468ULL },
    { -304, -1073,  10120112665365530918ULL },    { -303, -1070,  12650140831706913647ULL },
    { -302, -1067,  15812676039633642059ULL },    { -301, -1063,   9882922524771026287ULL },
    { -300, -1060,  12353653155963782858ULL },    { -299, -1057,  15442066444954728573ULL },
    { -298, -1053,   9651291528096705358ULL },    { -297, -1050,  12064114410120881698ULL },
    { -296, -1047,  15080143012651102122ULL },    { -295, -1043,   9425089382906938826ULL },
    { -294, -1040,  11781361728633673533ULL },    { -293, -1037,  14726702160792091916ULL },
    { -292, -1034,  18408377700990114895ULL },    { -291, -1030,  11505236063118821809ULL },
    { -290, -1027,  14381545078898527262ULL },    { -289, -1024,  17976931348623159077ULL },
    { -288, -1020,  11235582092889474423ULL },    { -287, -1017,  14044477616111843029ULL },
    { -286, -1014,  17555597020139803786ULL },    { -285, -1010,  10972248137587377367ULL },
    { -284, -1007,  13715310171984221708ULL },    { -283, -1004,  17144137714980277135ULL },
    { -282, -1000,  10715086071862673209ULL },    { -281,  -997,  13393857589828341512ULL },
    { -280,  -994,  16742321987285426890ULL },    { -279,  -990,  10463951242053391806ULL },
    { -278,  -987,  13079939052566739758ULL },    { -277,  -984,  16349923815708424697ULL },
    { -276,  -980,  10218702384817765436ULL },    { -275,  -977,  12773377981022206795ULL },
    { -274,  -974,  15966722476277758493ULL },    { -273,  -970,   9979201547673599058ULL },
    { -272,  -967,  12474001934591998823ULL },    { -271,  -964,  15592502418239998529ULL },
    { -270,  -960,   9745314011399999080ULL },    { -269,  -957,  12181642514249998850ULL },
    { -268,  -954,  15227053142812498563ULL },    { -267,  -950,   9516908214257811602ULL },
    { -266,  -947,  11896135267822264502ULL },    { -265,  -944,  14870169084777830628ULL },
    { -264,  -940,   9293855677986144142ULL },    { -263,  -937,  11617319597482680178ULL },
    { -262,  -934,  14521649496853350223ULL },    { -261,  -931,  18152061871066687778ULL },
    { -260,  -927,  11345038669416679861ULL },    { -259,  -924,  14181298336770849827ULL },
    { -258,  -921,  17726622920963562283ULL },    { -257,  -917,  11079139325602226427ULL },
    { -256,  -914,  13848924157002783034ULL },    { -255,  -911,  17311155196253478792ULL },
    { -254,  -907,  10819471997658424245ULL },    { -253,  -904,  13524339997073030307ULL },
    { -252,  -901,  16905424996341287883ULL },    { -251,  -897,  10565890622713304927ULL },
    { -250,  -894,  13207363278391631159ULL },    { -249,  -891,  16509204097989538949ULL },
    { -248,  -887,  10318252561243461843ULL },    { -247,  -884,  12897815701554327304ULL },
    { -246,  -881,  16122269626942909129ULL },    { -245,  -877,  10076418516839318206ULL },
    { -244,  -874,  12595523146049147757ULL },    { -243,  -871,  15744403932561434697ULL },
    { -242,  -867,   9840252457850896685ULL },    { -241,  -864,  12300315572313620857ULL },
    { -240,  -861,  15375394465392026071ULL },    { -239,  -857,   9609621540870016294ULL },
    { -238,  -854,  12012026926087520368ULL },    { -237,  -851,  15015033657609400460ULL },
    { -236,  -847,   9384396036005875287ULL },    { -235,  -844,  11730495045007344109ULL },
    { -234,  -841,  14663118806259180137ULL },    { -233,  -838,  18328898507823975171ULL },
    { -232,  -834,  11455561567389984482ULL },    { -231,  -831,  14319451959237480602ULL },
    { -230,  -828,  17899314949046850753ULL },    { -229,  -824,  11187071843154281720ULL },
    { -228,  -821,  13983839803942852151ULL },    { -227,  -818,  17479799754928565188ULL },
    { -226,  -814,  10924874846830353243ULL },    { -225,  -811,  13656093558537941553ULL },
    { -224,  -808,  17070116948172426942ULL },    { -223,  -804,  10668823092607766839ULL },
    { -222,  -801,  13336028865759708548ULL },    { -221,  -798,  16670036082199635685ULL },
    { -220,  -794,  10418772551374772303ULL },    { -219,  -791,  13023465689218465379ULL },
    { -218,  -788,  16279332111523081724ULL },    { -217,  -784,  10174582569701926077ULL },
    { -216,  -781,  12718228212127407597ULL },    { -215,  -778,  15897785265159259496ULL },
    { -214,  -774,   9936115790724537185ULL },    { -213,  -771,  12420144738405671481ULL },
    { -212,  -768,  15525180923007089351ULL },    { -211,  -764,   9703238076879430845ULL },
    { -210,  -761,  12129047596099288556ULL },    { -209,  -758,  15161309495124110695ULL },
    { -208,  -754,   9475818434452569184ULL },    { -207,  -751,  11844773043065711480ULL },
    { -206,  -748,  14805966303832139350ULL },    { -205,  -744,   9253728939895087094ULL },
    { -204,  -741,  11567161174868858868ULL },    { -203,  -738,  14458951468586073584ULL },
    { -202,  -735,  18073689335732591980ULL },    { -201,  -731,  11296055834832869988ULL },
    { -200,  -728,  14120069793541087485ULL },    { -199,  -725,  17650087241926359356ULL },
    { -198,  -721,  11031304526203974597ULL },    { -197,  -718,  13789130657754968247ULL },
    { -196,  -715,  17236413322193710309ULL },    { -195,  -711,  10772758326371068943ULL },
    { -194,  -708,  13465947907963836179ULL },    { -193,  -705,  16832434884954795223ULL },
    { -192,  -701,  10520271803096747014ULL },    { -191,  -698,  13150339753870933768ULL },
    { -190,  -695,  16437924692338667210ULL },    { -189,  -691,  10273702932711667006ULL },
    { -188,  -688,  12842128665889583758ULL },    { -187,  -685,  16052660832361979697ULL },
    { -186,  -681,  10032913020226237311ULL },    { -185,  -678,  12541141275282796639ULL },
    { -184,  -675,  15676426594103495798ULL },    { -183,  -671,   9797766621314684874ULL },
    { -182,  -668,  12247208276643356092ULL },    { -181,  -665,  15309010345804195115ULL },
    { -180,  -661,   9568131466127621947ULL },    { -179,  -658,  11960164332659527434ULL },
    { -178,  -655,  14950205415824409292ULL },    { -177,  -651,   9343878384890255808ULL },
    { -176,  -648,  11679847981112819760ULL },    { -175,  -645,  14599809976391024700ULL },
    { -174,  -642,  18249762470488780875ULL },    { -173,  -638,  11406101544055488047ULL },
    { -172,  -635,  14257626930069360058ULL },    { -171,  -632,  17822033662586700073ULL },
    { -170,  -628,  11138771039116687546ULL },    { -169,  -625,  13923463798895859432ULL },
    { -168,  -622,  17404329748619824290ULL },    { -167,  -618,  10877706092887390181ULL },
    { -166,  -615,  13597132616109237726ULL },    { -165,  -612,  16996415770136547158ULL },
    { -164,  -608,  10622759856335341974ULL },    { -163,  -605,  13278449820419177467ULL },
    { -162,  -602,  16598062275523971834ULL },    { -161,  -598,  10373788922202482396ULL },
    { -160,  -595,  12967236152753102995ULL },    { -159,  -592,  16209045190941378744ULL },
    { -158,  -588,  10130653244338361715ULL },    { -157,  -585,  12663316555422952144ULL },
    { -156,  -582,  15829145694278690180ULL },    { -155,  -578,   9893216058924181362ULL },
    { -154,  -575,  12366520073655226703ULL },    { -153,  -572,  15458150092069033379ULL },
    { -152,  -568,   9661343807543145862ULL },    { -151,  -565,  12076679759428932327ULL },
    { -150,  -562,  15095849699286165409ULL },    { -149,  -558,   9434906062053853381ULL },
    { -148,  -555,  11793632577567316726ULL },    { -147,  -552,  14742040721959145907ULL },
    { -146,  -549,  18427550902448932384ULL },    { -145,  -545,  11517219314030582740ULL },
    { -144,  -542,  14396524142538228425ULL },    { -143,  -539,  17995655178172785531ULL },
    { -142,  -535,  11247284486357990957ULL },    { -141,  -532,  14059105607947488696ULL },
    { -140,  -529,  17573882009934360870ULL },    { -139,  -525,  10983676256208975544ULL },
    { -138,  -522,  13729595320261219430ULL },    { -137,  -519,  17161994150326524287ULL },
    { -136,  -515,  10726246343954077680ULL },    { -135,  -512,  13407807929942597100ULL },
    { -134,  -509,  16759759912428246374ULL },    { -133,  -505,  10474849945267653984ULL },
    { -132,  -502,  13093562431584567480ULL },    { -131,  -499,  16366953039480709350ULL },
    { -130,  -495,  10229345649675443344ULL },    { -129,  -492,  12786682062094304180ULL },
    { -128,  -489,  15983352577617880225ULL },    { -127,  -485,   9989595361011175140ULL },
    { -126,  -482,  12486994201263968926ULL },    { -125,  -479,  15608742751579961157ULL },
    { -124,  -475,   9755464219737475723ULL },    { -123,  -472,  12194330274671844654ULL },
    { -122,  -469,  15242912843339805817ULL },    { -121,  -465,   9526820527087378636ULL },
    { -120,  -462,  11908525658859223295ULL },    { -119,  -459,  14885657073574029118ULL },
    { -118,  -455,   9303535670983768199ULL },    { -117,  -452,  11629419588729710249ULL },
    { -116,  -449,  14536774485912137811ULL },    { -115,  -446,  18170968107390172264ULL },
    { -114,  -442,  11356855067118857665ULL },    { -113,  -439,  14196068833898572081ULL },
    { -112,  -436,  17745086042373215101ULL },    { -111,  -432,  11090678776483259438ULL },
    { -110,  -429,  13863348470604074298ULL },    { -109,  -426,  17329185588255092872ULL },
    { -108,  -422,  10830740992659433045ULL },    { -107,  -419,  13538426240824291307ULL },
    { -106,  -416,  16923032801030364133ULL },    { -105,  -412,  10576895500643977583ULL },
    { -104,  -409,  13221119375804971979ULL },    { -103,  -406,  16526399219756214974ULL },
    { -102,  -402,  10328999512347634359ULL },    { -101,  -399,  12911249390434542948ULL },
    { -100,  -396,  16139061738043178685ULL },    {  -99,  -392,  10086913586276986678ULL },
    {  -98,  -389,  12608641982846233348ULL },    {  -97,  -386,  15760802478557791685ULL },
    {  -96,  -382,   9850501549098619803ULL },    {  -95,  -379,  12313126936373274754ULL },
    {  -94,  -376,  15391408670466593442ULL },    {  -93,  -372,   9619630419041620901ULL },
    {  -92,  -369,  12024538023802026127ULL },    {  -91,  -366,  15030672529752532658ULL },
    {  -90,  -362,   9394170331095332912ULL },    {  -89,  -359,  11742712913869166139ULL },
    {  -88,  -356,  14678391142336457674ULL },    {  -87,  -353,  18347988927920572093ULL },
    {  -86,  -349,  11467493079950357558ULL },    {  -85,  -346,  14334366349937946948ULL },
    {  -84,  -343,  17917957937422433684ULL },    {  -83,  -339,  11198723710889021053ULL },
    {  -82,  -336,  13998404638611276316ULL },    {  -81,  -333,  17498005798264095395ULL },
    {  -80,  -329,  10936253623915059622ULL },    {  -79,  -326,  13670317029893824527ULL },
    {  -78,  -323,  17087896287367280659ULL },    {  -77,  -319,  10679935179604550412ULL },
    {  -76,  -316,  13349918974505688015ULL },    {  -75,  -313,  16687398718132110019ULL },
    {  -74,  -309,  10429624198832568762ULL },    {  -73,  -306,  13037030248540710952ULL },
    {  -72,  -303,  16296287810675888690ULL },    {  -71,  -299,  10185179881672430431ULL },
    {  -70,  -296,  12731474852090538039ULL },    {  -69,  -293,  15914343565113172549ULL },
    {  -68,  -289,   9946464728195732843ULL },    {  -67,  -286,  12433080910244666054ULL },
    {  -66,  -283,  15541351137805832567ULL },    {  -65,  -279,   9713344461128645355ULL },
    {  -64,  -276,  12141680576410806693ULL },    {  -63,  -273,  15177100720513508367ULL },
    {  -62,  -269,   9485687950320942729ULL },    {  -61,  -266,  11857109937901178411ULL },
    {  -60,  -263,  14821387422376473014ULL },    {  -59,  -259,   9263367138985295634ULL },
    {  -58,  -256,  11579208923731619542ULL },    {  -57,  -253,  14474011154664524428ULL },
    {  -56,  -250,  18092513943330655535ULL },    {  -55,  -246,  11307821214581659709ULL },
    {  -54,  -243,  14134776518227074637ULL },    {  -53,  -240,  17668470647783843296ULL },
    {  -52,  -236,  11042794154864902060ULL },    {  -51,  -233,  13803492693581127575ULL },
    {  -50,  -230,  17254365866976409469ULL },    {  -49,  -226,  10783978666860255918ULL },
    {  -48,  -223,  13479973333575319897ULL },    {  -47,  -220,  16849966666969149872ULL },
    {  -46,  -216,  10531229166855718670ULL },    {  -45,  -213,  13164036458569648337ULL },
    {  -44,  -210,  16455045573212060422ULL },    {  -43,  -206,  10284403483257537763ULL },
    {  -42,  -203,  12855504354071922204ULL },    {  -41,  -200,  16069380442589902755ULL },
    {  -40,  -196,  10043362776618689222ULL },    {  -39,  -193,  12554203470773361528ULL },
    {  -38,  -190,  15692754338466701910ULL },    {  -37,  -186,   9807971461541688693ULL },
    {  -36,  -183,  12259964326927110867ULL },    {  -35,  -180,  15324955408658888584ULL },
    {  -34,  -176,   9578097130411805365ULL },    {  -33,  -173,  11972621413014756706ULL },
    {  -32,  -170,  14965776766268445882ULL },    {  -31,  -166,   9353610478917778677ULL },
    {  -30,  -163,  11692013098647223346ULL },    {  -29,  -160,  14615016373309029182ULL },
    {  -28,  -157,  18268770466636286478ULL },    {  -27,  -153,  11417981541647679048ULL },
    {  -26,  -150,  14272476927059598811ULL },    {  -25,  -147,  17840596158824498513ULL },
    {  -24,  -143,  11150372599265311571ULL },    {  -23,  -140,  13937965749081639463ULL },
    {  -22,  -137,  17422457186352049329ULL },    {  -21,  -133,  10889035741470030831ULL },
    {  -20,  -130,  13611294676837538539ULL },    {  -19,  -127,  17014118346046923173ULL },
    {  -18,  -123,  10633823966279326983ULL },    {  -17,  -120,  13292279957849158729ULL },
    {  -16,  -117,  16615349947311448411ULL },    {  -15,  -113,  10384593717069655257ULL },
    {  -14,  -110,  12980742146337069071ULL },    {  -13,  -107,  16225927682921336339ULL },
    {  -12,  -103,  10141204801825835212ULL },    {  -11,  -100,  12676506002282294015ULL },
    {  -10,   -97,  15845632502852867519ULL },    {   -9,   -93,   9903520314283042199ULL },
    {   -8,   -90,  12379400392853802749ULL },    {   -7,   -87,  15474250491067253436ULL },
    {   -6,   -83,   9671406556917033398ULL },    {   -5,   -80,  12089258196146291747ULL },
    {   -4,   -77,  15111572745182864684ULL },    {   -3,   -73,   9444732965739290427ULL },
    {   -2,   -70,  11805916207174113034ULL },    {   -1,   -67,  14757395258967641293ULL },
    {    0,   -63,   9223372036854775808ULL },    {    1,   -60,  11529215046068469760ULL },
    {    2,   -57,  14411518807585587200ULL },    {    3,   -54,  18014398509481984000ULL },
    {    4,   -50,  11258999068426240000ULL },    {    5,   -47,  14073748835532800000ULL },
    {    6,   -44,  17592186044416000000ULL },    {    7,   -40,  10995116277760000000ULL },
    {    8,   -37,  13743895347200000000ULL },    {    9,   -34,  17179869184000000000ULL },
    {   10,   -30,  10737418240000000000ULL },    {   11,   -27,  13421772800000000000ULL },
    {   12,   -24,  16777216000000000000ULL },    {   13,   -20,  10485760000000000000ULL },
    {   14,   -17,  13107200000000000000ULL },    {   15,   -14,  16384000000000000000ULL },
    {   16,   -10,  10240000000000000000ULL },    {   17,    -7,  12800000000000000000ULL },
    {   18,    -4,  16000000000000000000ULL },    {   19,     0,  10000000000000000000ULL },
    {   20,     3,  12500000000000000000ULL },    {   21,     6,  15625000000000000000ULL },
    {   22,    10,   9765625000000000000ULL },    {   23,    13,  12207031250000000000ULL },
    {   24,    16,  15258789062500000000ULL },    {   25,    20,   9536743164062500000ULL },
    {   26,    23,  11920928955078125000ULL },    {   27,    26,  14901161193847656250ULL },
    {   28,    30,   9313225746154785156ULL },    {   29,    33,  11641532182693481445ULL },
    {   30,    36,  14551915228366851807ULL },    {   31,    39,  18189894035458564758ULL },
    {   32,    43,  11368683772161602974ULL },    {   33,    46,  14210854715202003717ULL },
    {   34,    49,  17763568394002504647ULL },    {   35,    53,  11102230246251565404ULL },
    {   36,    56,  13877787807814456755ULL },    {   37,    59,  17347234759768070944ULL },
    {   38,    63,  10842021724855044340ULL },    {   39,    66,  13552527156068805425ULL },
    {   40,    69,  16940658945086006781ULL },    {   41,    73,  10587911840678754238ULL },
    {   42,    76,  13234889800848442798ULL },    {   43,    79,  16543612251060553497ULL },
    {   44,    83,  10339757656912845936ULL },    {   45,    86,  12924697071141057420ULL },
    {   46,    89,  16155871338926321775ULL },    {   47,    93,  10097419586828951109ULL },
    {   48,    96,  12621774483536188887ULL },    {   49,    99,  15777218104420236108ULL },
    {   50,   103,   9860761315262647568ULL },    {   51,   106,  12325951644078309460ULL },
    {   52,   109,  15407439555097886824ULL },    {   53,   113,   9629649721936179265ULL },
    {   54,   116,  12037062152420224082ULL },    {   55,   119,  15046327690525280102ULL },
    {   56,   123,   9403954806578300064ULL },    {   57,   126,  11754943508222875080ULL },
    {   58,   129,  14693679385278593850ULL },    {   59,   132,  18367099231598242312ULL },
    {   60,   136,  11479437019748901445ULL },    {   61,   139,  14349296274686126806ULL },
    {   62,   142,  17936620343357658508ULL },    {   63,   146,  11210387714598536567ULL },
    {   64,   149,  14012984643248170709ULL },    {   65,   152,  17516230804060213387ULL },
    {   66,   156,  10947644252537633367ULL },    {   67,   159,  13684555315672041708ULL },
    {   68,   162,  17105694144590052135ULL },    {   69,   166,  10691058840368782585ULL },
    {   70,   169,  13363823550460978231ULL },    {   71,   172,  16704779438076222788ULL },
    {   72,   176,  10440487148797639243ULL },    {   73,   179,  13050608935997049053ULL },
    {   74,   182,  16313261169996311317ULL },    {   75,   186,  10195788231247694573ULL },
    {   76,   189,  12744735289059618216ULL },    {   77,   192,  15930919111324522770ULL },
    {   78,   196,   9956824444577826731ULL },    {   79,   199,  12446030555722283414ULL },
    {   80,   202,  15557538194652854268ULL },    {   81,   206,   9723461371658033917ULL },
    {   82,   209,  12154326714572542397ULL },    {   83,   212,  15192908393215677996ULL },
    {   84,   216,   9495567745759798747ULL },    {   85,   219,  11869459682199748434ULL },
    {   86,   222,  14836824602749685543ULL },    {   87,   226,   9273015376718553464ULL },
    {   88,   229,  11591269220898191830ULL },    {   89,   232,  14489086526122739788ULL },
    {   90,   235,  18111358157653424735ULL },    {   91,   239,  11319598848533390459ULL },
    {   92,   242,  14149498560666738074ULL },    {   93,   245,  17686873200833422593ULL },
    {   94,   249,  11054295750520889120ULL },    {   95,   252,  13817869688151111401ULL },
    {   96,   255,  17272337110188889251ULL },    {   97,   259,  10795210693868055782ULL },
    {   98,   262,  13494013367335069727ULL },    {   99,   265,  16867516709168837159ULL },
    {  100,   269,  10542197943230523224ULL },    {  101,   272,  13177747429038154030ULL },
    {  102,   275,  16472184286297692538ULL },    {  103,   279,  10295115178936057836ULL },
    {  104,   282,  12868893973670072295ULL },    {  105,   285,  16086117467087590369ULL },
    {  106,   289,  10053823416929743981ULL },    {  107,   292,  12567279271162179976ULL },
    {  108,   295,  15709099088952724970ULL },    {  109,   299,   9818186930595453106ULL },
    {  110,   302,  12272733663244316383ULL },    {  111,   305,  15340917079055395478ULL },
    {  112,   309,   9588073174409622174ULL },    {  113,   312,  11985091468012027718ULL },
    {  114,   315,  14981364335015034647ULL },    {  115,   319,   9363352709384396654ULL },
    {  116,   322,  11704190886730495818ULL },    {  117,   325,  14630238608413119772ULL },
    {  118,   328,  18287798260516399715ULL },    {  119,   332,  11429873912822749822ULL },
    {  120,   335,  14287342391028437278ULL },    {  121,   338,  17859177988785546597ULL },
    {  122,   342,  11161986242990966623ULL },    {  123,   345,  13952482803738708279ULL },
    {  124,   348,  17440603504673385349ULL },    {  125,   352,  10900377190420865843ULL },
    {  126,   355,  13625471488026082304ULL },    {  127,   358,  17031839360032602880ULL },
    {  128,   362,  10644899600020376800ULL },    {  129,   365,  13306124500025471000ULL },
    {  130,   368,  16632655625031838750ULL },    {  131,   372,  10395409765644899219ULL },
    {  132,   375,  12994262207056124023ULL },    {  133,   378,  16242827758820155029ULL },
    {  134,   382,  10151767349262596893ULL },    {  135,   385,  12689709186578246116ULL },
    {  136,   388,  15862136483222807645ULL },    {  137,   392,   9913835302014254778ULL },
    {  138,   395,  12392294127517818473ULL },    {  139,   398,  15490367659397273091ULL },
    {  140,   402,   9681479787123295682ULL },    {  141,   405,  12101849733904119603ULL },
    {  142,   408,  15127312167380149503ULL },    {  143,   412,   9454570104612593439ULL },
    {  144,   415,  11818212630765741799ULL },    {  145,   418,  14772765788457177249ULL },
    {  146,   422,   9232978617785735781ULL },    {  147,   425,  11541223272232169726ULL },
    {  148,   428,  14426529090290212157ULL },    {  149,   431,  18033161362862765197ULL },
    {  150,   435,  11270725851789228248ULL },    {  151,   438,  14088407314736535310ULL },
    {  152,   441,  17610509143420669137ULL },    {  153,   445,  11006568214637918211ULL },
    {  154,   448,  13758210268297397764ULL },    {  155,   451,  17197762835371747205ULL },
    {  156,   455,  10748601772107342003ULL },    {  157,   458,  13435752215134177504ULL },
    {  158,   461,  16794690268917721879ULL },    {  159,   465,  10496681418073576175ULL },
    {  160,   468,  13120851772591970218ULL },    {  161,   471,  16401064715739962773ULL },
    {  162,   475,  10250665447337476733ULL },    {  163,   478,  12813331809171845916ULL },
    {  164,   481,  16016664761464807395ULL },    {  165,   485,  10010415475915504622ULL },
    {  166,   488,  12513019344894380778ULL },    {  167,   491,  15641274181117975972ULL },
    {  168,   495,   9775796363198734983ULL },    {  169,   498,  12219745453998418728ULL },
    {  170,   501,  15274681817498023410ULL },    {  171,   505,   9546676135936264631ULL },
    {  172,   508,  11933345169920330789ULL },    {  173,   511,  14916681462400413487ULL },
    {  174,   515,   9322925914000258429ULL },    {  175,   518,  11653657392500323036ULL },
    {  176,   521,  14567071740625403795ULL },    {  177,   524,  18208839675781754744ULL },
    {  178,   528,  11380524797363596715ULL },    {  179,   531,  14225655996704495894ULL },
    {  180,   534,  17782069995880619868ULL },    {  181,   538,  11113793747425387417ULL },
    {  182,   541,  13892242184281734272ULL },    {  183,   544,  17365302730352167839ULL },
    {  184,   548,  10853314206470104900ULL },    {  185,   551,  13566642758087631125ULL },
    {  186,   554,  16958303447609538906ULL },    {  187,   558,  10598939654755961816ULL },
    {  188,   561,  13248674568444952270ULL },    {  189,   564,  16560843210556190338ULL },
    {  190,   568,  10350527006597618961ULL },    {  191,   571,  12938158758247023701ULL },
    {  192,   574,  16172698447808779627ULL },    {  193,   578,  10107936529880487267ULL },
    {  194,   581,  12634920662350609083ULL },    {  195,   584,  15793650827938261354ULL },
    {  196,   588,   9871031767461413346ULL },    {  197,   591,  12338789709326766683ULL },
    {  198,   594,  15423487136658458354ULL },    {  199,   598,   9639679460411536471ULL },
    {  200,   601,  12049599325514420589ULL },    {  201,   604,  15061999156893025736ULL },
    {  202,   608,   9413749473058141085ULL },    {  203,   611,  11767186841322676356ULL },
    {  204,   614,  14708983551653345445ULL },    {  205,   617,  18386229439566681806ULL },
    {  206,   621,  11491393399729176129ULL },    {  207,   624,  14364241749661470161ULL },
    {  208,   627,  17955302187076837702ULL },    {  209,   631,  11222063866923023564ULL },
    {  210,   634,  14027579833653779454ULL },    {  211,   637,  17534474792067224318ULL },
    {  212,   641,  10959046745042015199ULL },    {  213,   644,  13698808431302518998ULL },
    {  214,   647,  17123510539128148748ULL },    {  215,   651,  10702194086955092968ULL },
    {  216,   654,  13377742608693866209ULL },    {  217,   657,  16722178260867332762ULL },
    {  218,   661,  10451361413042082976ULL },    {  219,   664,  13064201766302603720ULL },
    {  220,   667,  16330252207878254650ULL },    {  221,   671,  10206407629923909156ULL },
    {  222,   674,  12758009537404886445ULL },    {  223,   677,  15947511921756108057ULL },
    {  224,   681,   9967194951097567536ULL },    {  225,   684,  12458993688871959419ULL },
    {  226,   687,  15573742111089949274ULL },    {  227,   691,   9733588819431218296ULL },
    {  228,   694,  12166986024289022870ULL },    {  229,   697,  15208732530361278588ULL },
    {  230,   701,   9505457831475799118ULL },    {  231,   704,  11881822289344748897ULL },
    {  232,   707,  14852277861680936121ULL },    {  233,   711,   9282673663550585076ULL },
    {  234,   714,  11603342079438231345ULL },    {  235,   717,  14504177599297789181ULL },
    {  236,   720,  18130221999122236476ULL },    {  237,   724,  11331388749451397798ULL },
    {  238,   727,  14164235936814247247ULL },    {  239,   730,  17705294921017809059ULL },
    {  240,   734,  11065809325636130662ULL },    {  241,   737,  13832261657045163327ULL },
    {  242,   740,  17290327071306454159ULL },    {  243,   744,  10806454419566533849ULL },
    {  244,   747,  13508068024458167312ULL },    {  245,   750,  16885085030572709140ULL },
    {  246,   754,  10553178144107943212ULL },    {  247,   757,  13191472680134929015ULL },
    {  248,   760,  16489340850168661269ULL },    {  249,   764,  10305838031355413293ULL },
    {  250,   767,  12882297539194266616ULL },    {  251,   770,  16102871923992833271ULL },
    {  252,   774,  10064294952495520794ULL },    {  253,   777,  12580368690619400993ULL },
    {  254,   780,  15725460863274251241ULL },    {  255,   784,   9828413039546407025ULL },
    {  256,   787,  12285516299433008782ULL },    {  257,   790,  15356895374291260977ULL },
    {  258,   794,   9598059608932038111ULL },    {  259,   797,  11997574511165047639ULL },
    {  260,   800,  14996968138956309548ULL },    {  261,   804,   9373105086847693468ULL },
    {  262,   807,  11716381358559616835ULL },    {  263,   810,  14645476698199521043ULL },
    {  264,   813,  18306845872749401304ULL },    {  265,   817,  11441778670468375815ULL },
    {  266,   820,  14302223338085469769ULL },    {  267,   823,  17877779172606837211ULL },
    {  268,   827,  11173611982879273257ULL },    {  269,   830,  13967014978599091571ULL },
    {  270,   833,  17458768723248864464ULL },    {  271,   837,  10911730452030540290ULL },
    {  272,   840,  13639663065038175362ULL },    {  273,   843,  17049578831297719203ULL },
    {  274,   847,  10655986769561074502ULL },    {  275,   850,  13319983461951343127ULL },
    {  276,   853,  16649979327439178909ULL },    {  277,   857,  10406237079649486818ULL },
    {  278,   860,  13007796349561858523ULL },    {  279,   863,  16259745436952323153ULL },
    {  280,   867,  10162340898095201971ULL },    {  281,   870,  12702926122619002464ULL },
    {  282,   873,  15878657653273753079ULL },    {  283,   877,   9924161033296095675ULL },
    {  284,   880,  12405201291620119593ULL },    {  285,   883,  15506501614525149492ULL },
    {  286,   887,   9691563509078218432ULL },    {  287,   890,  12114454386347773040ULL },
    {  288,   893,  15143067982934716300ULL },    {  289,   897,   9464417489334197688ULL },
    {  290,   900,  11830521861667747110ULL },    {  291,   903,  14788152327084683887ULL },
    {  292,   907,   9242595204427927429ULL },    {  293,   910,  11553244005534909287ULL }
};

// Table: powers of two in binary representation.
// 2^binary_exponent ~= decimal_mantissa * 10^decimal_exponent.
// 0.1 < decimal_mantissa < 1, mantissa was premultiplied by 2^64 and rounded to nearest integer.
// Covers entire range of IEEE 754 double, including denormals, plus small spare.
struct  power_of_two
{
    int32_t   binary_exponent;
    int32_t   decimal_exponent;
    uint64_t  decimal_mantissa;
};
static const struct power_of_two  powers_of_two_[] = {
    { -1140, -343,  12351641146031163604ULL },    { -1139, -342,   2470328229206232721ULL },
    { -1138, -342,   4940656458412465442ULL },    { -1137, -342,   9881312916824930884ULL },
    { -1136, -341,   1976262583364986177ULL },    { -1135, -341,   3952525166729972353ULL },
    { -1134, -341,   7905050333459944707ULL },    { -1133, -341,  15810100666919889414ULL },
    { -1132, -340,   3162020133383977883ULL },    { -1131, -340,   6324040266767955765ULL },
    { -1130, -340,  12648080533535911531ULL },    { -1129, -339,   2529616106707182306ULL },
    { -1128, -339,   5059232213414364612ULL },    { -1127, -339,  10118464426828729225ULL },
    { -1126, -338,   2023692885365745845ULL },    { -1125, -338,   4047385770731491690ULL },
    { -1124, -338,   8094771541462983380ULL },    { -1123, -338,  16189543082925966760ULL },
    { -1122, -337,   3237908616585193352ULL },    { -1121, -337,   6475817233170386704ULL },
    { -1120, -337,  12951634466340773408ULL },    { -1119, -336,   2590326893268154682ULL },
    { -1118, -336,   5180653786536309363ULL },    { -1117, -336,  10361307573072618726ULL },
    { -1116, -335,   2072261514614523745ULL },    { -1115, -335,   4144523029229047490ULL },
    { -1114, -335,   8289046058458094981ULL },    { -1113, -335,  16578092116916189962ULL },
    { -1112, -334,   3315618423383237992ULL },    { -1111, -334,   6631236846766475985ULL },
    { -1110, -334,  13262473693532951969ULL },    { -1109, -333,   2652494738706590394ULL },
    { -1108, -333,   5304989477413180788ULL },    { -1107, -333,  10609978954826361576ULL },
    { -1106, -332,   2121995790965272315ULL },    { -1105, -332,   4243991581930544630ULL },
    { -1104, -332,   8487983163861089260ULL },    { -1103, -332,  16975966327722178521ULL },
    { -1102, -331,   3395193265544435704ULL },    { -1101, -331,   6790386531088871408ULL },
    { -1100, -331,  13580773062177742817ULL },    { -1099, -330,   2716154612435548563ULL },
    { -1098, -330,   5432309224871097127ULL },    { -1097, -330,  10864618449742194253ULL },
    { -1096, -329,   2172923689948438851ULL },    { -1095, -329,   4345847379896877701ULL },
    { -1094, -329,   8691694759793755403ULL },    { -1093, -329,  17383389519587510805ULL },
    { -1092, -328,   3476677903917502161ULL },    { -1091, -328,   6953355807835004322ULL },
    { -1090, -328,  13906711615670008644ULL },    { -1089, -327,   2781342323134001729ULL },
    { -1088, -327,   5562684646268003458ULL },    { -1087, -327,  11125369292536006915ULL },
    { -1086, -326,   2225073858507201383ULL },    { -1085, -326,   4450147717014402766ULL },
    { -1084, -326,   8900295434028805532ULL },    { -1083, -326,  17800590868057611065ULL },
    { -1082, -325,   3560118173611522213ULL },    { -1081, -325,   7120236347223044426ULL },
    { -1080, -325,  14240472694446088852ULL },    { -1079, -324,   2848094538889217770ULL },
    { -1078, -324,   5696189077778435541ULL },    { -1077, -324,  11392378155556871081ULL },
    { -1076, -323,   2278475631111374216ULL },    { -1075, -323,   4556951262222748433ULL },
    { -1074, -323,   9113902524445496865ULL },    { -1073, -323,  18227805048890993730ULL },
    { -1072, -322,   3645561009778198746ULL },    { -1071, -322,   7291122019556397492ULL },
    { -1070, -322,  14582244039112794984ULL },    { -1069, -321,   2916448807822558997ULL },
    { -1068, -321,   5832897615645117994ULL },    { -1067, -321,  11665795231290235987ULL },
    { -1066, -320,   2333159046258047197ULL },    { -1065, -320,   4666318092516094395ULL },
    { -1064, -320,   9332636185032188790ULL },    { -1063, -319,   1866527237006437758ULL },
    { -1062, -319,   3733054474012875516ULL },    { -1061, -319,   7466108948025751032ULL },
    { -1060, -319,  14932217896051502064ULL },    { -1059, -318,   2986443579210300413ULL },
    { -1058, -318,   5972887158420600826ULL },    { -1057, -318,  11945774316841201651ULL },
    { -1056, -317,   2389154863368240330ULL },    { -1055, -317,   4778309726736480660ULL },
    { -1054, -317,   9556619453472961321ULL },    { -1053, -316,   1911323890694592264ULL },
    { -1052, -316,   3822647781389184528ULL },    { -1051, -316,   7645295562778369057ULL },
    { -1050, -316,  15290591125556738113ULL },    { -1049, -315,   3058118225111347623ULL },
    { -1048, -315,   6116236450222695245ULL },    { -1047, -315,  12232472900445390491ULL },
    { -1046, -314,   2446494580089078098ULL },    { -1045, -314,   4892989160178156196ULL },
    { -1044, -314,   9785978320356312393ULL },    { -1043, -313,   1957195664071262479ULL },
    { -1042, -313,   3914391328142524957ULL },    { -1041, -313,   7828782656285049914ULL },
    { -1040, -313,  15657565312570099828ULL },    { -1039, -312,   3131513062514019966ULL },
    { -1038, -312,   6263026125028039931ULL },    { -1037, -312,  12526052250056079862ULL },
    { -1036, -311,   2505210450011215972ULL },    { -1035, -311,   5010420900022431945ULL },
    { -1034, -311,  10020841800044863890ULL },    { -1033, -310,   2004168360008972778ULL },
    { -1032, -310,   4008336720017945556ULL },    { -1031, -310,   8016673440035891112ULL },
    { -1030, -310,  16033346880071782224ULL },    { -1029, -309,   3206669376014356445ULL },
    { -1028, -309,   6413338752028712890ULL },    { -1027, -309,  12826677504057425779ULL },
    { -1026, -308,   2565335500811485156ULL },    { -1025, -308,   5130671001622970312ULL },
    { -1024, -308,  10261342003245940623ULL },    { -1023, -307,   2052268400649188125ULL },
    { -1022, -307,   4104536801298376249ULL },    { -1021, -307,   8209073602596752499ULL },
    { -1020, -307,  16418147205193504997ULL },    { -1019, -306,   3283629441038700999ULL },
    { -1018, -306,   6567258882077401999ULL },    { -1017, -306,  13134517764154803998ULL },
    { -1016, -305,   2626903552830960800ULL },    { -1015, -305,   5253807105661921599ULL },
    { -1014, -305,  10507614211323843198ULL },    { -1013, -304,   2101522842264768640ULL },
    { -1012, -304,   4203045684529537279ULL },    { -1011, -304,   8406091369059074559ULL },
    { -1010, -304,  16812182738118149117ULL },    { -1009, -303,   3362436547623629823ULL },
    { -1008, -303,   6724873095247259647ULL },    { -1007, -303,  13449746190494519294ULL },
    { -1006, -302,   2689949238098903859ULL },    { -1005, -302,   5379898476197807718ULL },
    { -1004, -302,  10759796952395615435ULL },    { -1003, -301,   2151959390479123087ULL },
    { -1002, -301,   4303918780958246174ULL },    { -1001, -301,   8607837561916492348ULL },
    { -1000, -301,  17215675123832984696ULL },    {  -999, -300,   3443135024766596939ULL },
    {  -998, -300,   6886270049533193878ULL },    {  -997, -300,  13772540099066387757ULL },
    {  -996, -299,   2754508019813277551ULL },    {  -995, -299,   5509016039626555103ULL },
    {  -994, -299,  11018032079253110206ULL },    {  -993, -298,   2203606415850622041ULL },
    {  -992, -298,   4407212831701244082ULL },    {  -991, -298,   8814425663402488164ULL },
    {  -990, -298,  17628851326804976329ULL },    {  -989, -297,   3525770265360995266ULL },
    {  -988, -297,   7051540530721990532ULL },    {  -987, -297,  14103081061443981063ULL },
    {  -986, -296,   2820616212288796213ULL },    {  -985, -296,   5641232424577592425ULL },
    {  -984, -296,  11282464849155184850ULL },    {  -983, -295,   2256492969831036970ULL },
    {  -982, -295,   4512985939662073940ULL },    {  -981, -295,   9025971879324147880ULL },
    {  -980, -295,  18051943758648295761ULL },    {  -979, -294,   3610388751729659152ULL },
    {  -978, -294,   7220777503459318304ULL },    {  -977, -294,  14441555006918636609ULL },
    {  -976, -293,   2888311001383727322ULL },    {  -975, -293,   5776622002767454643ULL },
    {  -974, -293,  11553244005534909287ULL },    {  -973, -292,   2310648801106981857ULL },
    {  -972, -292,   4621297602213963715ULL },    {  -971, -292,   9242595204427927429ULL },
    {  -970, -291,   1848519040885585486ULL },    {  -969, -291,   3697038081771170972ULL },
    {  -968, -291,   7394076163542341944ULL },    {  -967, -291,  14788152327084683887ULL },
    {  -966, -290,   2957630465416936777ULL },    {  -965, -290,   5915260930833873555ULL },
    {  -964, -290,  11830521861667747110ULL },    {  -963, -289,   2366104372333549422ULL },
    {  -962, -289,   4732208744667098844ULL },    {  -961, -289,   9464417489334197688ULL },
    {  -960, -288,   1892883497866839538ULL },    {  -959, -288,   3785766995733679075ULL },
    {  -958, -288,   7571533991467358150ULL },    {  -957, -288,  15143067982934716300ULL },
    {  -956, -287,   3028613596586943260ULL },    {  -955, -287,   6057227193173886520ULL },
    {  -954, -287,  12114454386347773040ULL },    {  -953, -286,   2422890877269554608ULL },
    {  -952, -286,   4845781754539109216ULL },    {  -951, -286,   9691563509078218432ULL },
    {  -950, -285,   1938312701815643686ULL },    {  -949, -285,   3876625403631287373ULL },
    {  -948, -285,   7753250807262574746ULL },    {  -947, -285,  15506501614525149492ULL },
    {  -946, -284,   3101300322905029898ULL },    {  -945, -284,   6202600645810059797ULL },
    {  -944, -284,  12405201291620119593ULL },    {  -943, -283,   2481040258324023919ULL },
    {  -942, -283,   4962080516648047837ULL },    {  -941, -283,   9924161033296095675ULL },
    {  -940, -282,   1984832206659219135ULL },    {  -939, -282,   3969664413318438270ULL },
    {  -938, -282,   7939328826636876540ULL },    {  -937, -282,  15878657653273753079ULL },
    {  -936, -281,   3175731530654750616ULL },    {  -935, -281,   6351463061309501232ULL },
    {  -934, -281,  12702926122619002464ULL },    {  -933, -280,   2540585224523800493ULL },
    {  -932, -280,   5081170449047600985ULL },    {  -931, -280,  10162340898095201971ULL },
    {  -930, -279,   2032468179619040394ULL },    {  -929, -279,   4064936359238080788ULL },
    {  -928, -279,   8129872718476161577ULL },    {  -927, -279,  16259745436952323153ULL },
    {  -926, -278,   3251949087390464631ULL },    {  -925, -278,   6503898174780929261ULL },
    {  -924, -278,  13007796349561858523ULL },    {  -923, -277,   2601559269912371705ULL },
    {  -922, -277,   5203118539824743409ULL },    {  -921, -277,  10406237079649486818ULL },
    {  -920, -276,   2081247415929897364ULL },    {  -919, -276,   4162494831859794727ULL },
    {  -918, -276,   8324989663719589455ULL },    {  -917, -276,  16649979327439178909ULL },
    {  -916, -275,   3329995865487835782ULL },    {  -915, -275,   6659991730975671564ULL },
    {  -914, -275,  13319983461951343127ULL },    {  -913, -274,   2663996692390268625ULL },
    {  -912, -274,   5327993384780537251ULL },    {  -911, -274,  10655986769561074502ULL },
    {  -910, -273,   2131197353912214900ULL },    {  -909, -273,   4262394707824429801ULL },
    {  -908, -273,   8524789415648859601ULL },    {  -907, -273,  17049578831297719203ULL },
    {  -906, -272,   3409915766259543841ULL },    {  -905, -272,   6819831532519087681ULL },
    {  -904, -272,  13639663065038175362ULL },    {  -903, -271,   2727932613007635072ULL },
    {  -902, -271,   5455865226015270145ULL },    {  -901, -271,  10911730452030540290ULL },
    {  -900, -270,   2182346090406108058ULL },    {  -899, -270,   4364692180812216116ULL },
    {  -898, -270,   8729384361624432232ULL },    {  -897, -270,  17458768723248864464ULL },
    {  -896, -269,   3491753744649772893ULL },    {  -895, -269,   6983507489299545785ULL },
    {  -894, -269,  13967014978599091571ULL },    {  -893, -268,   2793402995719818314ULL },
    {  -892, -268,   5586805991439636628ULL },    {  -891, -268,  11173611982879273257ULL },
    {  -890, -267,   2234722396575854651ULL },    {  -889, -267,   4469444793151709303ULL },
    {  -888, -267,   8938889586303418605ULL },    {  -887, -267,  17877779172606837211ULL },
    {  -886, -266,   3575555834521367442ULL },    {  -885, -266,   7151111669042734884ULL },
    {  -884, -266,  14302223338085469769ULL },    {  -883, -265,   2860444667617093954ULL },
    {  -882, -265,   5720889335234187907ULL },    {  -881, -265,  11441778670468375815ULL },
    {  -880, -264,   2288355734093675163ULL },    {  -879, -264,   4576711468187350326ULL },
    {  -878, -264,   9153422936374700652ULL },    {  -877, -264,  18306845872749401304ULL },
    {  -876, -263,   3661369174549880261ULL },    {  -875, -263,   7322738349099760522ULL },
    {  -874, -263,  14645476698199521043ULL },    {  -873, -262,   2929095339639904209ULL },
    {  -872, -262,   5858190679279808417ULL },    {  -871, -262,  11716381358559616835ULL },
    {  -870, -261,   2343276271711923367ULL },    {  -869, -261,   4686552543423846734ULL },
    {  -868, -261,   9373105086847693468ULL },    {  -867, -260,   1874621017369538694ULL },
    {  -866, -260,   3749242034739077387ULL },    {  -865, -260,   7498484069478154774ULL },
    {  -864, -260,  14996968138956309548ULL },    {  -863, -259,   2999393627791261910ULL },
    {  -862, -259,   5998787255582523819ULL },    {  -861, -259,  11997574511165047639ULL },
    {  -860, -258,   2399514902233009528ULL },    {  -859, -258,   4799029804466019055ULL },
    {  -858, -258,   9598059608932038111ULL },    {  -857, -257,   1919611921786407622ULL },
    {  -856, -257,   3839223843572815244ULL },    {  -855, -257,   7678447687145630489ULL },
    {  -854, -257,  15356895374291260977ULL },    {  -853, -256,   3071379074858252195ULL },
    {  -852, -256,   6142758149716504391ULL },    {  -851, -256,  12285516299433008782ULL },
    {  -850, -255,   2457103259886601756ULL },    {  -849, -255,   4914206519773203513ULL },
    {  -848, -255,   9828413039546407025ULL },    {  -847, -254,   1965682607909281405ULL },
    {  -846, -254,   3931365215818562810ULL },    {  -845, -254,   7862730431637125620ULL },
    {  -844, -254,  15725460863274251241ULL },    {  -843, -253,   3145092172654850248ULL },
    {  -842, -253,   6290184345309700496ULL },    {  -841, -253,  12580368690619400993ULL },
    {  -840, -252,   2516073738123880199ULL },    {  -839, -252,   5032147476247760397ULL },
    {  -838, -252,  10064294952495520794ULL },    {  -837, -251,   2012858990499104159ULL },
    {  -836, -251,   4025717980998208318ULL },    {  -835, -251,   8051435961996416635ULL },
    {  -834, -251,  16102871923992833271ULL },    {  -833, -250,   3220574384798566654ULL },
    {  -832, -250,   6441148769597133308ULL },    {  -831, -250,  12882297539194266616ULL },
    {  -830, -249,   2576459507838853323ULL },    {  -829, -249,   5152919015677706647ULL },
    {  -828, -249,  10305838031355413293ULL },    {  -827, -248,   2061167606271082659ULL },
    {  -826, -248,   4122335212542165317ULL },    {  -825, -248,   8244670425084330635ULL },
    {  -824, -248,  16489340850168661269ULL },    {  -823, -247,   3297868170033732254ULL },
    {  -822, -247,   6595736340067464508ULL },    {  -821, -247,  13191472680134929015ULL },
    {  -820, -246,   2638294536026985803ULL },    {  -819, -246,   5276589072053971606ULL },
    {  -818, -246,  10553178144107943212ULL },    {  -817, -245,   2110635628821588642ULL },
    {  -816, -245,   4221271257643177285ULL },    {  -815, -245,   8442542515286354570ULL },
    {  -814, -245,  16885085030572709140ULL },    {  -813, -244,   3377017006114541828ULL },
    {  -812, -244,   6754034012229083656ULL },    {  -811, -244,  13508068024458167312ULL },
    {  -810, -243,   2701613604891633462ULL },    {  -809, -243,   5403227209783266925ULL },
    {  -808, -243,  10806454419566533849ULL },    {  -807, -242,   2161290883913306770ULL },
    {  -806, -242,   4322581767826613540ULL },    {  -805, -242,   8645163535653227079ULL },
    {  -804, -242,  17290327071306454159ULL },    {  -803, -241,   3458065414261290832ULL },
    {  -802, -241,   6916130828522581664ULL },    {  -801, -241,  13832261657045163327ULL },
    {  -800, -240,   2766452331409032665ULL },    {  -799, -240,   5532904662818065331ULL },
    {  -798, -240,  11065809325636130662ULL },    {  -797, -239,   2213161865127226132ULL },
    {  -796, -239,   4426323730254452265ULL },    {  -795, -239,   8852647460508904529ULL },
    {  -794, -239,  17705294921017809059ULL },    {  -793, -238,   3541058984203561812ULL },
    {  -792, -238,   7082117968407123623ULL },    {  -791, -238,  14164235936814247247ULL },
    {  -790, -237,   2832847187362849449ULL },    {  -789, -237,   5665694374725698899ULL },
    {  -788, -237,  11331388749451397798ULL },    {  -787, -236,   2266277749890279560ULL },
    {  -786, -236,   4532555499780559119ULL },    {  -785, -236,   9065110999561118238ULL },
    {  -784, -236,  18130221999122236476ULL },    {  -783, -235,   3626044399824447295ULL },
    {  -782, -235,   7252088799648894590ULL },    {  -781, -235,  14504177599297789181ULL },
    {  -780, -234,   2900835519859557836ULL },    {  -779, -234,   5801671039719115672ULL },
    {  -778, -234,  11603342079438231345ULL },    {  -777, -233,   2320668415887646269ULL },
    {  -776, -233,   4641336831775292538ULL },    {  -775, -233,   9282673663550585076ULL },
    {  -774, -232,   1856534732710117015ULL },    {  -773, -232,   3713069465420234030ULL },
    {  -772, -232,   7426138930840468061ULL },    {  -771, -232,  14852277861680936121ULL },
    {  -770, -231,   2970455572336187224ULL },    {  -769, -231,   5940911144672374448ULL },
    {  -768, -231,  11881822289344748897ULL },    {  -767, -230,   2376364457868949779ULL },
    {  -766, -230,   4752728915737899559ULL },    {  -765, -230,   9505457831475799118ULL },
    {  -764, -229,   1901091566295159824ULL },    {  -763, -229,   3802183132590319647ULL },
    {  -762, -229,   7604366265180639294ULL },    {  -761, -229,  15208732530361278588ULL },
    {  -760, -228,   3041746506072255718ULL },    {  -759, -228,   6083493012144511435ULL },
    {  -758, -228,  12166986024289022870ULL },    {  -757, -227,   2433397204857804574ULL },
    {  -756, -227,   4866794409715609148ULL },    {  -755, -227,   9733588819431218296ULL },
    {  -754, -226,   1946717763886243659ULL },    {  -753, -226,   3893435527772487319ULL },
    {  -752, -226,   7786871055544974637ULL },    {  -751, -226,  15573742111089949274ULL },
    {  -750, -225,   3114748422217989855ULL },    {  -749, -225,   6229496844435979710ULL },
    {  -748, -225,  12458993688871959419ULL },    {  -747, -224,   2491798737774391884ULL },
    {  -746, -224,   4983597475548783768ULL },    {  -745, -224,   9967194951097567536ULL },
    {  -744, -223,   1993438990219513507ULL },    {  -743, -223,   3986877980439027014ULL },
    {  -742, -223,   7973755960878054028ULL },    {  -741, -223,  15947511921756108057ULL },
    {  -740, -222,   3189502384351221611ULL },    {  -739, -222,   6379004768702443223ULL },
    {  -738, -222,  12758009537404886445ULL },    {  -737, -221,   2551601907480977289ULL },
    {  -736, -221,   5103203814961954578ULL },    {  -735, -221,  10206407629923909156ULL },
    {  -734, -220,   2041281525984781831ULL },    {  -733, -220,   4082563051969563663ULL },
    {  -732, -220,   8165126103939127325ULL },    {  -731, -220,  16330252207878254650ULL },
    {  -730, -219,   3266050441575650930ULL },    {  -729, -219,   6532100883151301860ULL },
    {  -728, -219,  13064201766302603720ULL },    {  -727, -218,   2612840353260520744ULL },
    {  -726, -218,   5225680706521041488ULL },    {  -725, -218,  10451361413042082976ULL },
    {  -724, -217,   2090272282608416595ULL },    {  -723, -217,   4180544565216833190ULL },
    {  -722, -217,   8361089130433666381ULL },    {  -721, -217,  16722178260867332762ULL },
    {  -720, -216,   3344435652173466552ULL },    {  -719, -216,   6688871304346933105ULL },
    {  -718, -216,  13377742608693866209ULL },    {  -717, -215,   2675548521738773242ULL },
    {  -716, -215,   5351097043477546484ULL },    {  -715, -215,  10702194086955092968ULL },
    {  -714, -214,   2140438817391018594ULL },    {  -713, -214,   4280877634782037187ULL },
    {  -712, -214,   8561755269564074374ULL },    {  -711, -214,  17123510539128148748ULL },
    {  -710, -213,   3424702107825629750ULL },    {  -709, -213,   6849404215651259499ULL },
    {  -708, -213,  13698808431302518998ULL },    {  -707, -212,   2739761686260503800ULL },
    {  -706, -212,   5479523372521007599ULL },    {  -705, -212,  10959046745042015199ULL },
    {  -704, -211,   2191809349008403040ULL },    {  -703, -211,   4383618698016806080ULL },
    {  -702, -211,   8767237396033612159ULL },    {  -701, -211,  17534474792067224318ULL },
    {  -700, -210,   3506894958413444864ULL },    {  -699, -210,   7013789916826889727ULL },
    {  -698, -210,  14027579833653779454ULL },    {  -697, -209,   2805515966730755891ULL },
    {  -696, -209,   5611031933461511782ULL },    {  -695, -209,  11222063866923023564ULL },
    {  -694, -208,   2244412773384604713ULL },    {  -693, -208,   4488825546769209425ULL },
    {  -692, -208,   8977651093538418851ULL },    {  -691, -208,  17955302187076837702ULL },
    {  -690, -207,   3591060437415367540ULL },    {  -689, -207,   7182120874830735081ULL },
    {  -688, -207,  14364241749661470161ULL },    {  -687, -206,   2872848349932294032ULL },
    {  -686, -206,   5745696699864588065ULL },    {  -685, -206,  11491393399729176129ULL },
    {  -684, -205,   2298278679945835226ULL },    {  -683, -205,   4596557359891670452ULL },
    {  -682, -205,   9193114719783340903ULL },    {  -681, -205,  18386229439566681806ULL },
    {  -680, -204,   3677245887913336361ULL },    {  -679, -204,   7354491775826672723ULL },
    {  -678, -204,  14708983551653345445ULL },    {  -677, -203,   2941796710330669089ULL },
    {  -676, -203,   5883593420661338178ULL },    {  -675, -203,  11767186841322676356ULL },
    {  -674, -202,   2353437368264535271ULL },    {  -673, -202,   4706874736529070542ULL },
    {  -672, -202,   9413749473058141085ULL },    {  -671, -201,   1882749894611628217ULL },
    {  -670, -201,   3765499789223256434ULL },    {  -669, -201,   7530999578446512868ULL },
    {  -668, -201,  15061999156893025736ULL },    {  -667, -200,   3012399831378605147ULL },
    {  -666, -200,   6024799662757210294ULL },    {  -665, -200,  12049599325514420589ULL },
    {  -664, -199,   2409919865102884118ULL },    {  -663, -199,   4819839730205768235ULL },
    {  -662, -199,   9639679460411536471ULL },    {  -661, -198,   1927935892082307294ULL },
    {  -660, -198,   3855871784164614588ULL },    {  -659, -198,   7711743568329229177ULL },
    {  -658, -198,  15423487136658458354ULL },    {  -657, -197,   3084697427331691671ULL },
    {  -656, -197,   6169394854663383341ULL },    {  -655, -197,  12338789709326766683ULL },
    {  -654, -196,   2467757941865353337ULL },    {  -653, -196,   4935515883730706673ULL },
    {  -652, -196,   9871031767461413346ULL },    {  -651, -195,   1974206353492282669ULL },
    {  -650, -195,   3948412706984565339ULL },    {  -649, -195,   7896825413969130677ULL },
    {  -648, -195,  15793650827938261354ULL },    {  -647, -194,   3158730165587652271ULL },
    {  -646, -194,   6317460331175304542ULL },    {  -645, -194,  12634920662350609083ULL },
    {  -644, -193,   2526984132470121817ULL },    {  -643, -193,   5053968264940243633ULL },
    {  -642, -193,  10107936529880487267ULL },    {  -641, -192,   2021587305976097453ULL },
    {  -640, -192,   4043174611952194907ULL },    {  -639, -192,   8086349223904389813ULL },
    {  -638, -192,  16172698447808779627ULL },    {  -637, -191,   3234539689561755925ULL },
    {  -636, -191,   6469079379123511851ULL },    {  -635, -191,  12938158758247023701ULL },
    {  -634, -190,   2587631751649404740ULL },    {  -633, -190,   5175263503298809480ULL },
    {  -632, -190,  10350527006597618961ULL },    {  -631, -189,   2070105401319523792ULL },
    {  -630, -189,   4140210802639047584ULL },    {  -629, -189,   8280421605278095169ULL },
    {  -628, -189,  16560843210556190338ULL },    {  -627, -188,   3312168642111238068ULL },
    {  -626, -188,   6624337284222476135ULL },    {  -625, -188,  13248674568444952270ULL },
    {  -624, -187,   2649734913688990454ULL },    {  -623, -187,   5299469827377980908ULL },
    {  -622, -187,  10598939654755961816ULL },    {  -621, -186,   2119787930951192363ULL },
    {  -620, -186,   4239575861902384726ULL },    {  -619, -186,   8479151723804769453ULL },
    {  -618, -186,  16958303447609538906ULL },    {  -617, -185,   3391660689521907781ULL },
    {  -616, -185,   6783321379043815562ULL },    {  -615, -185,  13566642758087631125ULL },
    {  -614, -184,   2713328551617526225ULL },    {  -613, -184,   5426657103235052450ULL },
    {  -612, -184,  10853314206470104900ULL },    {  -611, -183,   2170662841294020980ULL },
    {  -610, -183,   4341325682588041960ULL },    {  -609, -183,   8682651365176083920ULL },
    {  -608, -183,  17365302730352167839ULL },    {  -607, -182,   3473060546070433568ULL },
    {  -606, -182,   6946121092140867136ULL },    {  -605, -182,  13892242184281734272ULL },
    {  -604, -181,   2778448436856346854ULL },    {  -603, -181,   5556896873712693709ULL },
    {  -602, -181,  11113793747425387417ULL },    {  -601, -180,   2222758749485077483ULL },
    {  -600, -180,   4445517498970154967ULL },    {  -599, -180,   8891034997940309934ULL },
    {  -598, -180,  17782069995880619868ULL },    {  -597, -179,   3556413999176123974ULL },
    {  -596, -179,   7112827998352247947ULL },    {  -595, -179,  14225655996704495894ULL },
    {  -594, -178,   2845131199340899179ULL },    {  -593, -178,   5690262398681798358ULL },
    {  -592, -178,  11380524797363596715ULL },    {  -591, -177,   2276104959472719343ULL },
    {  -590, -177,   4552209918945438686ULL },    {  -589, -177,   9104419837890877372ULL },
    {  -588, -177,  18208839675781754744ULL },    {  -587, -176,   3641767935156350949ULL },
    {  -586, -176,   7283535870312701898ULL },    {  -585, -176,  14567071740625403795ULL },
    {  -584, -175,   2913414348125080759ULL },    {  -583, -175,   5826828696250161518ULL },
    {  -582, -175,  11653657392500323036ULL },    {  -581, -174,   2330731478500064607ULL },
    {  -580, -174,   4661462957000129215ULL },    {  -579, -174,   9322925914000258429ULL },
    {  -578, -173,   1864585182800051686ULL },    {  -577, -173,   3729170365600103372ULL },
    {  -576, -173,   7458340731200206743ULL },    {  -575, -173,  14916681462400413487ULL },
    {  -574, -172,   2983336292480082697ULL },    {  -573, -172,   5966672584960165395ULL },
    {  -572, -172,  11933345169920330789ULL },    {  -571, -171,   2386669033984066158ULL },
    {  -570, -171,   4773338067968132316ULL },    {  -569, -171,   9546676135936264631ULL },
    {  -568, -170,   1909335227187252926ULL },    {  -567, -170,   3818670454374505853ULL },
    {  -566, -170,   7637340908749011705ULL },    {  -565, -170,  15274681817498023410ULL },
    {  -564, -169,   3054936363499604682ULL },    {  -563, -169,   6109872726999209364ULL },
    {  -562, -169,  12219745453998418728ULL },    {  -561, -168,   2443949090799683746ULL },
    {  -560, -168,   4887898181599367491ULL },    {  -559, -168,   9775796363198734983ULL },
    {  -558, -167,   1955159272639746997ULL },    {  -557, -167,   3910318545279493993ULL },
    {  -556, -167,   7820637090558987986ULL },    {  -555, -167,  15641274181117975972ULL },
    {  -554, -166,   3128254836223595194ULL },    {  -553, -166,   6256509672447190389ULL },
    {  -552, -166,  12513019344894380778ULL },    {  -551, -165,   2502603868978876156ULL },
    {  -550, -165,   5005207737957752311ULL },    {  -549, -165,  10010415475915504622ULL },
    {  -548, -164,   2002083095183100924ULL },    {  -547, -164,   4004166190366201849ULL },
    {  -546, -164,   8008332380732403698ULL },    {  -545, -164,  16016664761464807395ULL },
    {  -544, -163,   3203332952292961479ULL },    {  -543, -163,   6406665904585922958ULL },
    {  -542, -163,  12813331809171845916ULL },    {  -541, -162,   2562666361834369183ULL },
    {  -540, -162,   5125332723668738367ULL },    {  -539, -162,  10250665447337476733ULL },
    {  -538, -161,   2050133089467495347ULL },    {  -537, -161,   4100266178934990693ULL },
    {  -536, -161,   8200532357869981386ULL },    {  -535, -161,  16401064715739962773ULL },
    {  -534, -160,   3280212943147992555ULL },    {  -533, -160,   6560425886295985109ULL },
    {  -532, -160,  13120851772591970218ULL },    {  -531, -159,   2624170354518394044ULL },
    {  -530, -159,   5248340709036788087ULL },    {  -529, -159,  10496681418073576175ULL },
    {  -528, -158,   2099336283614715235ULL },    {  -527, -158,   4198672567229430470ULL },
    {  -526, -158,   8397345134458860940ULL },    {  -525, -158,  16794690268917721879ULL },
    {  -524, -157,   3358938053783544376ULL },    {  -523, -157,   6717876107567088752ULL },
    {  -522, -157,  13435752215134177504ULL },    {  -521, -156,   2687150443026835501ULL },
    {  -520, -156,   5374300886053671001ULL },    {  -519, -156,  10748601772107342003ULL },
    {  -518, -155,   2149720354421468401ULL },    {  -517, -155,   4299440708842936801ULL },
    {  -516, -155,   8598881417685873602ULL },    {  -515, -155,  17197762835371747205ULL },
    {  -514, -154,   3439552567074349441ULL },    {  -513, -154,   6879105134148698882ULL },
    {  -512, -154,  13758210268297397764ULL },    {  -511, -153,   2751642053659479553ULL },
    {  -510, -153,   5503284107318959105ULL },    {  -509, -153,  11006568214637918211ULL },
    {  -508, -152,   2201313642927583642ULL },    {  -507, -152,   4402627285855167284ULL },
    {  -506, -152,   8805254571710334569ULL },    {  -505, -152,  17610509143420669137ULL },
    {  -504, -151,   3522101828684133827ULL },    {  -503, -151,   7044203657368267655ULL },
    {  -502, -151,  14088407314736535310ULL },    {  -501, -150,   2817681462947307062ULL },
    {  -500, -150,   5635362925894614124ULL },    {  -499, -150,  11270725851789228248ULL },
    {  -498, -149,   2254145170357845650ULL },    {  -497, -149,   4508290340715691299ULL },
    {  -496, -149,   9016580681431382598ULL },    {  -495, -149,  18033161362862765197ULL },
    {  -494, -148,   3606632272572553039ULL },    {  -493, -148,   7213264545145106079ULL },
    {  -492, -148,  14426529090290212157ULL },    {  -491, -147,   2885305818058042431ULL },
    {  -490, -147,   5770611636116084863ULL },    {  -489, -147,  11541223272232169726ULL },
    {  -488, -146,   2308244654446433945ULL },    {  -487, -146,   4616489308892867890ULL },
    {  -486, -146,   9232978617785735781ULL },    {  -485, -145,   1846595723557147156ULL },
    {  -484, -145,   3693191447114294312ULL },    {  -483, -145,   7386382894228588625ULL },
    {  -482, -145,  14772765788457177249ULL },    {  -481, -144,   2954553157691435450ULL },
    {  -480, -144,   5909106315382870900ULL },    {  -479, -144,  11818212630765741799ULL },
    {  -478, -143,   2363642526153148360ULL },    {  -477, -143,   4727285052306296720ULL },
    {  -476, -143,   9454570104612593439ULL },    {  -475, -142,   1890914020922518688ULL },
    {  -474, -142,   3781828041845037376ULL },    {  -473, -142,   7563656083690074752ULL },
    {  -472, -142,  15127312167380149503ULL },    {  -471, -141,   3025462433476029901ULL },
    {  -470, -141,   6050924866952059801ULL },    {  -469, -141,  12101849733904119603ULL },
    {  -468, -140,   2420369946780823921ULL },    {  -467, -140,   4840739893561647841ULL },
    {  -466, -140,   9681479787123295682ULL },    {  -465, -139,   1936295957424659136ULL },
    {  -464, -139,   3872591914849318273ULL },    {  -463, -139,   7745183829698636546ULL },
    {  -462, -139,  15490367659397273091ULL },    {  -461, -138,   3098073531879454618ULL },
    {  -460, -138,   6196147063758909237ULL },    {  -459, -138,  12392294127517818473ULL },
    {  -458, -137,   2478458825503563695ULL },    {  -457, -137,   4956917651007127389ULL },
    {  -456, -137,   9913835302014254778ULL },    {  -455, -136,   1982767060402850956ULL },
    {  -454, -136,   3965534120805701911ULL },    {  -453, -136,   7931068241611403823ULL },
    {  -452, -136,  15862136483222807645ULL },    {  -451, -135,   3172427296644561529ULL },
    {  -450, -135,   6344854593289123058ULL },    {  -449, -135,  12689709186578246116ULL },
    {  -448, -134,   2537941837315649223ULL },    {  -447, -134,   5075883674631298447ULL },
    {  -446, -134,  10151767349262596893ULL },    {  -445, -133,   2030353469852519379ULL },
    {  -444, -133,   4060706939705038757ULL },    {  -443, -133,   8121413879410077514ULL },
    {  -442, -133,  16242827758820155029ULL },    {  -441, -132,   3248565551764031006ULL },
    {  -440, -132,   6497131103528062012ULL },    {  -439, -132,  12994262207056124023ULL },
    {  -438, -131,   2598852441411224805ULL },    {  -437, -131,   5197704882822449609ULL },
    {  -436, -131,  10395409765644899219ULL },    {  -435, -130,   2079081953128979844ULL },
    {  -434, -130,   4158163906257959687ULL },    {  -433, -130,   8316327812515919375ULL },
    {  -432, -130,  16632655625031838750ULL },    {  -431, -129,   3326531125006367750ULL },
    {  -430, -129,   6653062250012735500ULL },    {  -429, -129,  13306124500025471000ULL },
    {  -428, -128,   2661224900005094200ULL },    {  -427, -128,   5322449800010188400ULL },
    {  -426, -128,  10644899600020376800ULL },    {  -425, -127,   2128979920004075360ULL },
    {  -424, -127,   4257959840008150720ULL },    {  -423, -127,   8515919680016301440ULL },
    {  -422, -127,  17031839360032602880ULL },    {  -421, -126,   3406367872006520576ULL },
    {  -420, -126,   6812735744013041152ULL },    {  -419, -126,  13625471488026082304ULL },
    {  -418, -125,   2725094297605216461ULL },    {  -417, -125,   5450188595210432921ULL },
    {  -416, -125,  10900377190420865843ULL },    {  -415, -124,   2180075438084173169ULL },
    {  -414, -124,   4360150876168346337ULL },    {  -413, -124,   8720301752336692674ULL },
    {  -412, -124,  17440603504673385349ULL },    {  -411, -123,   3488120700934677070ULL },
    {  -410, -123,   6976241401869354140ULL },    {  -409, -123,  13952482803738708279ULL },
    {  -408, -122,   2790496560747741656ULL },    {  -407, -122,   5580993121495483312ULL },
    {  -406, -122,  11161986242990966623ULL },    {  -405, -121,   2232397248598193325ULL },
    {  -404, -121,   4464794497196386649ULL },    {  -403, -121,   8929588994392773299ULL },
    {  -402, -121,  17859177988785546597ULL },    {  -401, -120,   3571835597757109319ULL },
    {  -400, -120,   7143671195514218639ULL },    {  -399, -120,  14287342391028437278ULL },
    {  -398, -119,   2857468478205687456ULL },    {  -397, -119,   5714936956411374911ULL },
    {  -396, -119,  11429873912822749822ULL },    {  -395, -118,   2285974782564549964ULL },
    {  -394, -118,   4571949565129099929ULL },    {  -393, -118,   9143899130258199858ULL },
    {  -392, -118,  18287798260516399715ULL },    {  -391, -117,   3657559652103279943ULL },
    {  -390, -117,   7315119304206559886ULL },    {  -389, -117,  14630238608413119772ULL },
    {  -388, -116,   2926047721682623954ULL },    {  -387, -116,   5852095443365247909ULL },
    {  -386, -116,  11704190886730495818ULL },    {  -385, -115,   2340838177346099164ULL },
    {  -384, -115,   4681676354692198327ULL },    {  -383, -115,   9363352709384396654ULL },
    {  -382, -114,   1872670541876879331ULL },    {  -381, -114,   3745341083753758662ULL },
    {  -380, -114,   7490682167507517323ULL },    {  -379, -114,  14981364335015034647ULL },
    {  -378, -113,   2996272867003006929ULL },    {  -377, -113,   5992545734006013859ULL },
    {  -376, -113,  11985091468012027718ULL },    {  -375, -112,   2397018293602405544ULL },
    {  -374, -112,   4794036587204811087ULL },    {  -373, -112,   9588073174409622174ULL },
    {  -372, -111,   1917614634881924435ULL },    {  -371, -111,   3835229269763848870ULL },
    {  -370, -111,   7670458539527697739ULL },    {  -369, -111,  15340917079055395478ULL },
    {  -368, -110,   3068183415811079096ULL },    {  -367, -110,   6136366831622158191ULL },
    {  -366, -110,  12272733663244316383ULL },    {  -365, -109,   2454546732648863277ULL },
    {  -364, -109,   4909093465297726553ULL },    {  -363, -109,   9818186930595453106ULL },
    {  -362, -108,   1963637386119090621ULL },    {  -361, -108,   3927274772238181242ULL },
    {  -360, -108,   7854549544476362485ULL },    {  -359, -108,  15709099088952724970ULL },
    {  -358, -107,   3141819817790544994ULL },    {  -357, -107,   6283639635581089988ULL },
    {  -356, -107,  12567279271162179976ULL },    {  -355, -106,   2513455854232435995ULL },
    {  -354, -106,   5026911708464871990ULL },    {  -353, -106,  10053823416929743981ULL },
    {  -352, -105,   2010764683385948796ULL },    {  -351, -105,   4021529366771897592ULL },
    {  -350, -105,   8043058733543795185ULL },    {  -349, -105,  16086117467087590369ULL },
    {  -348, -104,   3217223493417518074ULL },    {  -347, -104,   6434446986835036148ULL },
    {  -346, -104,  12868893973670072295ULL },    {  -345, -103,   2573778794734014459ULL },
    {  -344, -103,   5147557589468028918ULL },    {  -343, -103,  10295115178936057836ULL },
    {  -342, -102,   2059023035787211567ULL },    {  -341, -102,   4118046071574423135ULL },
    {  -340, -102,   8236092143148846269ULL },    {  -339, -102,  16472184286297692538ULL },
    {  -338, -101,   3294436857259538508ULL },    {  -337, -101,   6588873714519077015ULL },
    {  -336, -101,  13177747429038154030ULL },    {  -335, -100,   2635549485807630806ULL },
    {  -334, -100,   5271098971615261612ULL },    {  -333, -100,  10542197943230523224ULL },
    {  -332,  -99,   2108439588646104645ULL },    {  -331,  -99,   4216879177292209290ULL },
    {  -330,  -99,   8433758354584418579ULL },    {  -329,  -99,  16867516709168837159ULL },
    {  -328,  -98,   3373503341833767432ULL },    {  -327,  -98,   6747006683667534864ULL },
    {  -326,  -98,  13494013367335069727ULL },    {  -325,  -97,   2698802673467013945ULL },
    {  -324,  -97,   5397605346934027891ULL },    {  -323,  -97,  10795210693868055782ULL },
    {  -322,  -96,   2159042138773611156ULL },    {  -321,  -96,   4318084277547222313ULL },
    {  -320,  -96,   8636168555094444625ULL },    {  -319,  -96,  17272337110188889251ULL },
    {  -318,  -95,   3454467422037777850ULL },    {  -317,  -95,   6908934844075555700ULL },
    {  -316,  -95,  13817869688151111401ULL },    {  -315,  -94,   2763573937630222280ULL },
    {  -314,  -94,   5527147875260444560ULL },    {  -313,  -94,  11054295750520889120ULL },
    {  -312,  -93,   2210859150104177824ULL },    {  -311,  -93,   4421718300208355648ULL },
    {  -310,  -93,   8843436600416711296ULL },    {  -309,  -93,  17686873200833422593ULL },
    {  -308,  -92,   3537374640166684519ULL },    {  -307,  -92,   7074749280333369037ULL },
    {  -306,  -92,  14149498560666738074ULL },    {  -305,  -91,   2829899712133347615ULL },
    {  -304,  -91,   5659799424266695230ULL },    {  -303,  -91,  11319598848533390459ULL },
    {  -302,  -90,   2263919769706678092ULL },    {  -301,  -90,   4527839539413356184ULL },
    {  -300,  -90,   9055679078826712368ULL },    {  -299,  -90,  18111358157653424735ULL },
    {  -298,  -89,   3622271631530684947ULL },    {  -297,  -89,   7244543263061369894ULL },
    {  -296,  -89,  14489086526122739788ULL },    {  -295,  -88,   2897817305224547958ULL },
    {  -294,  -88,   5795634610449095915ULL },    {  -293,  -88,  11591269220898191830ULL },
    {  -292,  -87,   2318253844179638366ULL },    {  -291,  -87,   4636507688359276732ULL },
    {  -290,  -87,   9273015376718553464ULL },    {  -289,  -86,   1854603075343710693ULL },
    {  -288,  -86,   3709206150687421386ULL },    {  -287,  -86,   7418412301374842771ULL },
    {  -286,  -86,  14836824602749685543ULL },    {  -285,  -85,   2967364920549937109ULL },
    {  -284,  -85,   5934729841099874217ULL },    {  -283,  -85,  11869459682199748434ULL },
    {  -282,  -84,   2373891936439949687ULL },    {  -281,  -84,   4747783872879899374ULL },
    {  -280,  -84,   9495567745759798747ULL },    {  -279,  -83,   1899113549151959749ULL },
    {  -278,  -83,   3798227098303919499ULL },    {  -277,  -83,   7596454196607838998ULL },
    {  -276,  -83,  15192908393215677996ULL },    {  -275,  -82,   3038581678643135599ULL },
    {  -274,  -82,   6077163357286271198ULL },    {  -273,  -82,  12154326714572542397ULL },
    {  -272,  -81,   2430865342914508479ULL },    {  -271,  -81,   4861730685829016959ULL },
    {  -270,  -81,   9723461371658033917ULL },    {  -269,  -80,   1944692274331606783ULL },
    {  -268,  -80,   3889384548663213567ULL },    {  -267,  -80,   7778769097326427134ULL },
    {  -266,  -80,  15557538194652854268ULL },    {  -265,  -79,   3111507638930570854ULL },
    {  -264,  -79,   6223015277861141707ULL },    {  -263,  -79,  12446030555722283414ULL },
    {  -262,  -78,   2489206111144456683ULL },    {  -261,  -78,   4978412222288913366ULL },
    {  -260,  -78,   9956824444577826731ULL },    {  -259,  -77,   1991364888915565346ULL },
    {  -258,  -77,   3982729777831130693ULL },    {  -257,  -77,   7965459555662261385ULL },
    {  -256,  -77,  15930919111324522770ULL },    {  -255,  -76,   3186183822264904554ULL },
    {  -254,  -76,   6372367644529809108ULL },    {  -253,  -76,  12744735289059618216ULL },
    {  -252,  -75,   2548947057811923643ULL },    {  -251,  -75,   5097894115623847286ULL },
    {  -250,  -75,  10195788231247694573ULL },    {  -249,  -74,   2039157646249538915ULL },
    {  -248,  -74,   4078315292499077829ULL },    {  -247,  -74,   8156630584998155658ULL },
    {  -246,  -74,  16313261169996311317ULL },    {  -245,  -73,   3262652233999262263ULL },
    {  -244,  -73,   6525304467998524527ULL },    {  -243,  -73,  13050608935997049053ULL },
    {  -242,  -72,   2610121787199409811ULL },    {  -241,  -72,   5220243574398819621ULL },
    {  -240,  -72,  10440487148797639243ULL },    {  -239,  -71,   2088097429759527849ULL },
    {  -238,  -71,   4176194859519055697ULL },    {  -237,  -71,   8352389719038111394ULL },
    {  -236,  -71,  16704779438076222788ULL },    {  -235,  -70,   3340955887615244558ULL },
    {  -234,  -70,   6681911775230489115ULL },    {  -233,  -70,  13363823550460978231ULL },
    {  -232,  -69,   2672764710092195646ULL },    {  -231,  -69,   5345529420184391292ULL },
    {  -230,  -69,  10691058840368782585ULL },    {  -229,  -68,   2138211768073756517ULL },
    {  -228,  -68,   4276423536147513034ULL },    {  -227,  -68,   8552847072295026068ULL },
    {  -226,  -68,  17105694144590052135ULL },    {  -225,  -67,   3421138828918010427ULL },
    {  -224,  -67,   6842277657836020854ULL },    {  -223,  -67,  13684555315672041708ULL },
    {  -222,  -66,   2736911063134408342ULL },    {  -221,  -66,   5473822126268816683ULL },
    {  -220,  -66,  10947644252537633367ULL },    {  -219,  -65,   2189528850507526673ULL },
    {  -218,  -65,   4379057701015053347ULL },    {  -217,  -65,   8758115402030106693ULL },
    {  -216,  -65,  17516230804060213387ULL },    {  -215,  -64,   3503246160812042677ULL },
    {  -214,  -64,   7006492321624085355ULL },    {  -213,  -64,  14012984643248170709ULL },
    {  -212,  -63,   2802596928649634142ULL },    {  -211,  -63,   5605193857299268284ULL },
    {  -210,  -63,  11210387714598536567ULL },    {  -209,  -62,   2242077542919707313ULL },
    {  -208,  -62,   4484155085839414627ULL },    {  -207,  -62,   8968310171678829254ULL },
    {  -206,  -62,  17936620343357658508ULL },    {  -205,  -61,   3587324068671531702ULL },
    {  -204,  -61,   7174648137343063403ULL },    {  -203,  -61,  14349296274686126806ULL },
    {  -202,  -60,   2869859254937225361ULL },    {  -201,  -60,   5739718509874450723ULL },
    {  -200,  -60,  11479437019748901445ULL },    {  -199,  -59,   2295887403949780289ULL },
    {  -198,  -59,   4591774807899560578ULL },    {  -197,  -59,   9183549615799121156ULL },
    {  -196,  -59,  18367099231598242312ULL },    {  -195,  -58,   3673419846319648462ULL },
    {  -194,  -58,   7346839692639296925ULL },    {  -193,  -58,  14693679385278593850ULL },
    {  -192,  -57,   2938735877055718770ULL },    {  -191,  -57,   5877471754111437540ULL },
    {  -190,  -57,  11754943508222875080ULL },    {  -189,  -56,   2350988701644575016ULL },
    {  -188,  -56,   4701977403289150032ULL },    {  -187,  -56,   9403954806578300064ULL },
    {  -186,  -55,   1880790961315660013ULL },    {  -185,  -55,   3761581922631320025ULL },
    {  -184,  -55,   7523163845262640051ULL },    {  -183,  -55,  15046327690525280102ULL },
    {  -182,  -54,   3009265538105056020ULL },    {  -181,  -54,   6018531076210112041ULL },
    {  -180,  -54,  12037062152420224082ULL },    {  -179,  -53,   2407412430484044816ULL },
    {  -178,  -53,   4814824860968089633ULL },    {  -177,  -53,   9629649721936179265ULL },
    {  -176,  -52,   1925929944387235853ULL },    {  -175,  -52,   3851859888774471706ULL },
    {  -174,  -52,   7703719777548943412ULL },    {  -173,  -52,  15407439555097886824ULL },
    {  -172,  -51,   3081487911019577365ULL },    {  -171,  -51,   6162975822039154730ULL },
    {  -170,  -51,  12325951644078309460ULL },    {  -169,  -50,   2465190328815661892ULL },
    {  -168,  -50,   4930380657631323784ULL },    {  -167,  -50,   9860761315262647568ULL },
    {  -166,  -49,   1972152263052529514ULL },    {  -165,  -49,   3944304526105059027ULL },
    {  -164,  -49,   7888609052210118054ULL },    {  -163,  -49,  15777218104420236108ULL },
    {  -162,  -48,   3155443620884047222ULL },    {  -161,  -48,   6310887241768094443ULL },
    {  -160,  -48,  12621774483536188887ULL },    {  -159,  -47,   2524354896707237777ULL },
    {  -158,  -47,   5048709793414475555ULL },    {  -157,  -47,  10097419586828951109ULL },
    {  -156,  -46,   2019483917365790222ULL },    {  -155,  -46,   4038967834731580444ULL },
    {  -154,  -46,   8077935669463160887ULL },    {  -153,  -46,  16155871338926321775ULL },
    {  -152,  -45,   3231174267785264355ULL },    {  -151,  -45,   6462348535570528710ULL },
    {  -150,  -45,  12924697071141057420ULL },    {  -149,  -44,   2584939414228211484ULL },
    {  -148,  -44,   5169878828456422968ULL },    {  -147,  -44,  10339757656912845936ULL },
    {  -146,  -43,   2067951531382569187ULL },    {  -145,  -43,   4135903062765138374ULL },
    {  -144,  -43,   8271806125530276749ULL },    {  -143,  -43,  16543612251060553497ULL },
    {  -142,  -42,   3308722450212110699ULL },    {  -141,  -42,   6617444900424221399ULL },
    {  -140,  -42,  13234889800848442798ULL },    {  -139,  -41,   2646977960169688560ULL },
    {  -138,  -41,   5293955920339377119ULL },    {  -137,  -41,  10587911840678754238ULL },
    {  -136,  -40,   2117582368135750848ULL },    {  -135,  -40,   4235164736271501695ULL },
    {  -134,  -40,   8470329472543003391ULL },    {  -133,  -40,  16940658945086006781ULL },
    {  -132,  -39,   3388131789017201356ULL },    {  -131,  -39,   6776263578034402713ULL },
    {  -130,  -39,  13552527156068805425ULL },    {  -129,  -38,   2710505431213761085ULL },
    {  -128,  -38,   5421010862427522170ULL },    {  -127,  -38,  10842021724855044340ULL },
    {  -126,  -37,   2168404344971008868ULL },    {  -125,  -37,   4336808689942017736ULL },
    {  -124,  -37,   8673617379884035472ULL },    {  -123,  -37,  17347234759768070944ULL },
    {  -122,  -36,   3469446951953614189ULL },    {  -121,  -36,   6938893903907228378ULL },
    {  -120,  -36,  13877787807814456755ULL },    {  -119,  -35,   2775557561562891351ULL },
    {  -118,  -35,   5551115123125782702ULL },    {  -117,  -35,  11102230246251565404ULL },
    {  -116,  -34,   2220446049250313081ULL },    {  -115,  -34,   4440892098500626162ULL },
    {  -114,  -34,   8881784197001252323ULL },    {  -113,  -34,  17763568394002504647ULL },
    {  -112,  -33,   3552713678800500929ULL },    {  -111,  -33,   7105427357601001859ULL },
    {  -110,  -33,  14210854715202003717ULL },    {  -109,  -32,   2842170943040400743ULL },
    {  -108,  -32,   5684341886080801487ULL },    {  -107,  -32,  11368683772161602974ULL },
    {  -106,  -31,   2273736754432320595ULL },    {  -105,  -31,   4547473508864641190ULL },
    {  -104,  -31,   9094947017729282379ULL },    {  -103,  -31,  18189894035458564758ULL },
    {  -102,  -30,   3637978807091712952ULL },    {  -101,  -30,   7275957614183425903ULL },
    {  -100,  -30,  14551915228366851807ULL },    {   -99,  -29,   2910383045673370361ULL },
    {   -98,  -29,   5820766091346740723ULL },    {   -97,  -29,  11641532182693481445ULL },
    {   -96,  -28,   2328306436538696289ULL },    {   -95,  -28,   4656612873077392578ULL },
    {   -94,  -28,   9313225746154785156ULL },    {   -93,  -27,   1862645149230957031ULL },
    {   -92,  -27,   3725290298461914063ULL },    {   -91,  -27,   7450580596923828125ULL },
    {   -90,  -27,  14901161193847656250ULL },    {   -89,  -26,   2980232238769531250ULL },
    {   -88,  -26,   5960464477539062500ULL },    {   -87,  -26,  11920928955078125000ULL },
    {   -86,  -25,   2384185791015625000ULL },    {   -85,  -25,   4768371582031250000ULL },
    {   -84,  -25,   9536743164062500000ULL },    {   -83,  -24,   1907348632812500000ULL },
    {   -82,  -24,   3814697265625000000ULL },    {   -81,  -24,   7629394531250000000ULL },
    {   -80,  -24,  15258789062500000000ULL },    {   -79,  -23,   3051757812500000000ULL },
    {   -78,  -23,   6103515625000000000ULL },    {   -77,  -23,  12207031250000000000ULL },
    {   -76,  -22,   2441406250000000000ULL },    {   -75,  -22,   4882812500000000000ULL },
    {   -74,  -22,   9765625000000000000ULL },    {   -73,  -21,   1953125000000000000ULL },
    {   -72,  -21,   3906250000000000000ULL },    {   -71,  -21,   7812500000000000000ULL },
    {   -70,  -21,  15625000000000000000ULL },    {   -69,  -20,   3125000000000000000ULL },
    {   -68,  -20,   6250000000000000000ULL },    {   -67,  -20,  12500000000000000000ULL },
    {   -66,  -19,   2500000000000000000ULL },    {   -65,  -19,   5000000000000000000ULL },
    {   -64,  -19,  10000000000000000000ULL },    {   -63,  -18,   2000000000000000000ULL },
    {   -62,  -18,   4000000000000000000ULL },    {   -61,  -18,   8000000000000000000ULL },
    {   -60,  -18,  16000000000000000000ULL },    {   -59,  -17,   3200000000000000000ULL },
    {   -58,  -17,   6400000000000000000ULL },    {   -57,  -17,  12800000000000000000ULL },
    {   -56,  -16,   2560000000000000000ULL },    {   -55,  -16,   5120000000000000000ULL },
    {   -54,  -16,  10240000000000000000ULL },    {   -53,  -15,   2048000000000000000ULL },
    {   -52,  -15,   4096000000000000000ULL },    {   -51,  -15,   8192000000000000000ULL },
    {   -50,  -15,  16384000000000000000ULL },    {   -49,  -14,   3276800000000000000ULL },
    {   -48,  -14,   6553600000000000000ULL },    {   -47,  -14,  13107200000000000000ULL },
    {   -46,  -13,   2621440000000000000ULL },    {   -45,  -13,   5242880000000000000ULL },
    {   -44,  -13,  10485760000000000000ULL },    {   -43,  -12,   2097152000000000000ULL },
    {   -42,  -12,   4194304000000000000ULL },    {   -41,  -12,   8388608000000000000ULL },
    {   -40,  -12,  16777216000000000000ULL },    {   -39,  -11,   3355443200000000000ULL },
    {   -38,  -11,   6710886400000000000ULL },    {   -37,  -11,  13421772800000000000ULL },
    {   -36,  -10,   2684354560000000000ULL },    {   -35,  -10,   5368709120000000000ULL },
    {   -34,  -10,  10737418240000000000ULL },    {   -33,   -9,   2147483648000000000ULL },
    {   -32,   -9,   4294967296000000000ULL },    {   -31,   -9,   8589934592000000000ULL },
    {   -30,   -9,  17179869184000000000ULL },    {   -29,   -8,   3435973836800000000ULL },
    {   -28,   -8,   6871947673600000000ULL },    {   -27,   -8,  13743895347200000000ULL },
    {   -26,   -7,   2748779069440000000ULL },    {   -25,   -7,   5497558138880000000ULL },
    {   -24,   -7,  10995116277760000000ULL },    {   -23,   -6,   2199023255552000000ULL },
    {   -22,   -6,   4398046511104000000ULL },    {   -21,   -6,   8796093022208000000ULL },
    {   -20,   -6,  17592186044416000000ULL },    {   -19,   -5,   3518437208883200000ULL },
    {   -18,   -5,   7036874417766400000ULL },    {   -17,   -5,  14073748835532800000ULL },
    {   -16,   -4,   2814749767106560000ULL },    {   -15,   -4,   5629499534213120000ULL },
    {   -14,   -4,  11258999068426240000ULL },    {   -13,   -3,   2251799813685248000ULL },
    {   -12,   -3,   4503599627370496000ULL },    {   -11,   -3,   9007199254740992000ULL },
    {   -10,   -3,  18014398509481984000ULL },    {    -9,   -2,   3602879701896396800ULL },
    {    -8,   -2,   7205759403792793600ULL },    {    -7,   -2,  14411518807585587200ULL },
    {    -6,   -1,   2882303761517117440ULL },    {    -5,   -1,   5764607523034234880ULL },
    {    -4,   -1,  11529215046068469760ULL },    {    -3,    0,   2305843009213693952ULL },
    {    -2,    0,   4611686018427387904ULL },    {    -1,    0,   9223372036854775808ULL },
    {     0,    1,   1844674407370955162ULL },    {     1,    1,   3689348814741910323ULL },
    {     2,    1,   7378697629483820646ULL },    {     3,    1,  14757395258967641293ULL },
    {     4,    2,   2951479051793528259ULL },    {     5,    2,   5902958103587056517ULL },
    {     6,    2,  11805916207174113034ULL },    {     7,    3,   2361183241434822607ULL },
    {     8,    3,   4722366482869645214ULL },    {     9,    3,   9444732965739290427ULL },
    {    10,    4,   1888946593147858085ULL },    {    11,    4,   3777893186295716171ULL },
    {    12,    4,   7555786372591432342ULL },    {    13,    4,  15111572745182864684ULL },
    {    14,    5,   3022314549036572937ULL },    {    15,    5,   6044629098073145874ULL },
    {    16,    5,  12089258196146291747ULL },    {    17,    6,   2417851639229258349ULL },
    {    18,    6,   4835703278458516699ULL },    {    19,    6,   9671406556917033398ULL },
    {    20,    7,   1934281311383406680ULL },    {    21,    7,   3868562622766813359ULL },
    {    22,    7,   7737125245533626718ULL },    {    23,    7,  15474250491067253436ULL },
    {    24,    8,   3094850098213450687ULL },    {    25,    8,   6189700196426901374ULL },
    {    26,    8,  12379400392853802749ULL },    {    27,    9,   2475880078570760550ULL },
    {    28,    9,   4951760157141521100ULL },    {    29,    9,   9903520314283042199ULL },
    {    30,   10,   1980704062856608440ULL },    {    31,   10,   3961408125713216880ULL },
    {    32,   10,   7922816251426433759ULL },    {    33,   10,  15845632502852867519ULL },
    {    34,   11,   3169126500570573504ULL },    {    35,   11,   6338253001141147007ULL },
    {    36,   11,  12676506002282294015ULL },    {    37,   12,   2535301200456458803ULL },
    {    38,   12,   5070602400912917606ULL },    {    39,   12,  10141204801825835212ULL },
    {    40,   13,   2028240960365167042ULL },    {    41,   13,   4056481920730334085ULL },
    {    42,   13,   8112963841460668170ULL },    {    43,   13,  16225927682921336339ULL },
    {    44,   14,   3245185536584267268ULL },    {    45,   14,   6490371073168534536ULL },
    {    46,   14,  12980742146337069071ULL },    {    47,   15,   2596148429267413814ULL },
    {    48,   15,   5192296858534827629ULL },    {    49,   15,  10384593717069655257ULL },
    {    50,   16,   2076918743413931051ULL },    {    51,   16,   4153837486827862103ULL },
    {    52,   16,   8307674973655724206ULL },    {    53,   16,  16615349947311448411ULL },
    {    54,   17,   3323069989462289682ULL },    {    55,   17,   6646139978924579365ULL },
    {    56,   17,  13292279957849158729ULL },    {    57,   18,   2658455991569831746ULL },
    {    58,   18,   5316911983139663492ULL },    {    59,   18,  10633823966279326983ULL },
    {    60,   19,   2126764793255865397ULL },    {    61,   19,   4253529586511730793ULL },
    {    62,   19,   8507059173023461587ULL },    {    63,   19,  17014118346046923173ULL },
    {    64,   20,   3402823669209384635ULL },    {    65,   20,   6805647338418769269ULL },
    {    66,   20,  13611294676837538539ULL },    {    67,   21,   2722258935367507708ULL },
    {    68,   21,   5444517870735015415ULL },    {    69,   21,  10889035741470030831ULL },
    {    70,   22,   2177807148294006166ULL },    {    71,   22,   4355614296588012332ULL },
    {    72,   22,   8711228593176024665ULL },    {    73,   22,  17422457186352049329ULL },
    {    74,   23,   3484491437270409866ULL },    {    75,   23,   6968982874540819732ULL },
    {    76,   23,  13937965749081639463ULL },    {    77,   24,   2787593149816327893ULL },
    {    78,   24,   5575186299632655785ULL },    {    79,   24,  11150372599265311571ULL },
    {    80,   25,   2230074519853062314ULL },    {    81,   25,   4460149039706124628ULL },
    {    82,   25,   8920298079412249257ULL },    {    83,   25,  17840596158824498513ULL },
    {    84,   26,   3568119231764899703ULL },    {    85,   26,   7136238463529799405ULL },
    {    86,   26,  14272476927059598811ULL },    {    87,   27,   2854495385411919762ULL },
    {    88,   27,   5708990770823839524ULL },    {    89,   27,  11417981541647679048ULL },
    {    90,   28,   2283596308329535810ULL },    {    91,   28,   4567192616659071619ULL },
    {    92,   28,   9134385233318143239ULL },    {    93,   28,  18268770466636286478ULL },
    {    94,   29,   3653754093327257296ULL },    {    95,   29,   7307508186654514591ULL },
    {    96,   29,  14615016373309029182ULL },    {    97,   30,   2923003274661805836ULL },
    {    98,   30,   5846006549323611673ULL },    {    99,   30,  11692013098647223346ULL },
    {   100,   31,   2338402619729444669ULL },    {   101,   31,   4676805239458889338ULL },
    {   102,   31,   9353610478917778677ULL },    {   103,   32,   1870722095783555735ULL },
    {   104,   32,   3741444191567111471ULL },    {   105,   32,   7482888383134222941ULL },
    {   106,   32,  14965776766268445882ULL },    {   107,   33,   2993155353253689176ULL },
    {   108,   33,   5986310706507378353ULL },    {   109,   33,  11972621413014756706ULL },
    {   110,   34,   2394524282602951341ULL },    {   111,   34,   4789048565205902682ULL },
    {   112,   34,   9578097130411805365ULL },    {   113,   35,   1915619426082361073ULL },
    {   114,   35,   3831238852164722146ULL },    {   115,   35,   7662477704329444292ULL },
    {   116,   35,  15324955408658888584ULL },    {   117,   36,   3064991081731777717ULL },
    {   118,   36,   6129982163463555433ULL },    {   119,   36,  12259964326927110867ULL },
    {   120,   37,   2451992865385422173ULL },    {   121,   37,   4903985730770844347ULL },
    {   122,   37,   9807971461541688693ULL },    {   123,   38,   1961594292308337739ULL },
    {   124,   38,   3923188584616675477ULL },    {   125,   38,   7846377169233350955ULL },
    {   126,   38,  15692754338466701910ULL },    {   127,   39,   3138550867693340382ULL },
    {   128,   39,   6277101735386680764ULL },    {   129,   39,  12554203470773361528ULL },
    {   130,   40,   2510840694154672306ULL },    {   131,   40,   5021681388309344611ULL },
    {   132,   40,  10043362776618689222ULL },    {   133,   41,   2008672555323737844ULL },
    {   134,   41,   4017345110647475689ULL },    {   135,   41,   8034690221294951378ULL },
    {   136,   41,  16069380442589902755ULL },    {   137,   42,   3213876088517980551ULL },
    {   138,   42,   6427752177035961102ULL },    {   139,   42,  12855504354071922204ULL },
    {   140,   43,   2571100870814384441ULL },    {   141,   43,   5142201741628768882ULL },
    {   142,   43,  10284403483257537763ULL },    {   143,   44,   2056880696651507553ULL },
    {   144,   44,   4113761393303015105ULL },    {   145,   44,   8227522786606030211ULL },
    {   146,   44,  16455045573212060422ULL },    {   147,   45,   3291009114642412084ULL },
    {   148,   45,   6582018229284824169ULL },    {   149,   45,  13164036458569648337ULL },
    {   150,   46,   2632807291713929667ULL },    {   151,   46,   5265614583427859335ULL },
    {   152,   46,  10531229166855718670ULL },    {   153,   47,   2106245833371143734ULL },
    {   154,   47,   4212491666742287468ULL },    {   155,   47,   8424983333484574936ULL },
    {   156,   47,  16849966666969149872ULL },    {   157,   48,   3369993333393829974ULL },
    {   158,   48,   6739986666787659949ULL },    {   159,   48,  13479973333575319897ULL },
    {   160,   49,   2695994666715063979ULL },    {   161,   49,   5391989333430127959ULL },
    {   162,   49,  10783978666860255918ULL },    {   163,   50,   2156795733372051184ULL },
    {   164,   50,   4313591466744102367ULL },    {   165,   50,   8627182933488204734ULL },
    {   166,   50,  17254365866976409469ULL },    {   167,   51,   3450873173395281894ULL },
    {   168,   51,   6901746346790563787ULL },    {   169,   51,  13803492693581127575ULL },
    {   170,   52,   2760698538716225515ULL },    {   171,   52,   5521397077432451030ULL },
    {   172,   52,  11042794154864902060ULL },    {   173,   53,   2208558830972980412ULL },
    {   174,   53,   4417117661945960824ULL },    {   175,   53,   8834235323891921648ULL },
    {   176,   53,  17668470647783843296ULL },    {   177,   54,   3533694129556768659ULL },
    {   178,   54,   7067388259113537318ULL },    {   179,   54,  14134776518227074637ULL },
    {   180,   55,   2826955303645414927ULL },    {   181,   55,   5653910607290829855ULL },
    {   182,   55,  11307821214581659709ULL },    {   183,   56,   2261564242916331942ULL },
    {   184,   56,   4523128485832663884ULL },    {   185,   56,   9046256971665327767ULL },
    {   186,   56,  18092513943330655535ULL },    {   187,   57,   3618502788666131107ULL },
    {   188,   57,   7237005577332262214ULL },    {   189,   57,  14474011154664524428ULL },
    {   190,   58,   2894802230932904886ULL },    {   191,   58,   5789604461865809771ULL },
    {   192,   58,  11579208923731619542ULL },    {   193,   59,   2315841784746323908ULL },
    {   194,   59,   4631683569492647817ULL },    {   195,   59,   9263367138985295634ULL },
    {   196,   60,   1852673427797059127ULL },    {   197,   60,   3705346855594118254ULL },
    {   198,   60,   7410693711188236507ULL },    {   199,   60,  14821387422376473014ULL },
    {   200,   61,   2964277484475294603ULL },    {   201,   61,   5928554968950589206ULL },
    {   202,   61,  11857109937901178411ULL },    {   203,   62,   2371421987580235682ULL },
    {   204,   62,   4742843975160471365ULL },    {   205,   62,   9485687950320942729ULL },
    {   206,   63,   1897137590064188546ULL },    {   207,   63,   3794275180128377092ULL },
    {   208,   63,   7588550360256754183ULL },    {   209,   63,  15177100720513508367ULL },
    {   210,   64,   3035420144102701673ULL },    {   211,   64,   6070840288205403347ULL },
    {   212,   64,  12141680576410806693ULL },    {   213,   65,   2428336115282161339ULL },
    {   214,   65,   4856672230564322677ULL },    {   215,   65,   9713344461128645355ULL },
    {   216,   66,   1942668892225729071ULL },    {   217,   66,   3885337784451458142ULL },
    {   218,   66,   7770675568902916284ULL },    {   219,   66,  15541351137805832567ULL },
    {   220,   67,   3108270227561166513ULL },    {   221,   67,   6216540455122333027ULL },
    {   222,   67,  12433080910244666054ULL },    {   223,   68,   2486616182048933211ULL },
    {   224,   68,   4973232364097866422ULL },    {   225,   68,   9946464728195732843ULL },
    {   226,   69,   1989292945639146569ULL },    {   227,   69,   3978585891278293137ULL },
    {   228,   69,   7957171782556586274ULL },    {   229,   69,  15914343565113172549ULL },
    {   230,   70,   3182868713022634510ULL },    {   231,   70,   6365737426045269020ULL },
    {   232,   70,  12731474852090538039ULL },    {   233,   71,   2546294970418107608ULL },
    {   234,   71,   5092589940836215216ULL },    {   235,   71,  10185179881672430431ULL },
    {   236,   72,   2037035976334486086ULL },    {   237,   72,   4074071952668972173ULL },
    {   238,   72,   8148143905337944345ULL },    {   239,   72,  16296287810675888690ULL },
    {   240,   73,   3259257562135177738ULL },    {   241,   73,   6518515124270355476ULL },
    {   242,   73,  13037030248540710952ULL },    {   243,   74,   2607406049708142190ULL },
    {   244,   74,   5214812099416284381ULL },    {   245,   74,  10429624198832568762ULL },
    {   246,   75,   2085924839766513752ULL },    {   247,   75,   4171849679533027505ULL },
    {   248,   75,   8343699359066055009ULL },    {   249,   75,  16687398718132110019ULL },
    {   250,   76,   3337479743626422004ULL },    {   251,   76,   6674959487252844007ULL },
    {   252,   76,  13349918974505688015ULL },    {   253,   77,   2669983794901137603ULL },
    {   254,   77,   5339967589802275206ULL },    {   255,   77,  10679935179604550412ULL },
    {   256,   78,   2135987035920910082ULL },    {   257,   78,   4271974071841820165ULL },
    {   258,   78,   8543948143683640330ULL },    {   259,   78,  17087896287367280659ULL },
    {   260,   79,   3417579257473456132ULL },    {   261,   79,   6835158514946912264ULL },
    {   262,   79,  13670317029893824527ULL },    {   263,   80,   2734063405978764905ULL },
    {   264,   80,   5468126811957529811ULL },    {   265,   80,  10936253623915059622ULL },
    {   266,   81,   2187250724783011924ULL },    {   267,   81,   4374501449566023849ULL },
    {   268,   81,   8749002899132047697ULL },    {   269,   81,  17498005798264095395ULL },
    {   270,   82,   3499601159652819079ULL },    {   271,   82,   6999202319305638158ULL },
    {   272,   82,  13998404638611276316ULL },    {   273,   83,   2799680927722255263ULL },
    {   274,   83,   5599361855444510526ULL },    {   275,   83,  11198723710889021053ULL },
    {   276,   84,   2239744742177804211ULL },    {   277,   84,   4479489484355608421ULL },
    {   278,   84,   8958978968711216842ULL },    {   279,   84,  17917957937422433684ULL },
    {   280,   85,   3583591587484486737ULL },    {   281,   85,   7167183174968973474ULL },
    {   282,   85,  14334366349937946948ULL },    {   283,   86,   2866873269987589390ULL },
    {   284,   86,   5733746539975178779ULL },    {   285,   86,  11467493079950357558ULL },
    {   286,   87,   2293498615990071512ULL },    {   287,   87,   4586997231980143023ULL },
    {   288,   87,   9173994463960286046ULL },    {   289,   87,  18347988927920572093ULL },
    {   290,   88,   3669597785584114419ULL },    {   291,   88,   7339195571168228837ULL },
    {   292,   88,  14678391142336457674ULL },    {   293,   89,   2935678228467291535ULL },
    {   294,   89,   5871356456934583070ULL },    {   295,   89,  11742712913869166139ULL },
    {   296,   90,   2348542582773833228ULL },    {   297,   90,   4697085165547666456ULL },
    {   298,   90,   9394170331095332912ULL },    {   299,   91,   1878834066219066582ULL },
    {   300,   91,   3757668132438133165ULL },    {   301,   91,   7515336264876266329ULL },
    {   302,   91,  15030672529752532658ULL },    {   303,   92,   3006134505950506532ULL },
    {   304,   92,   6012269011901013063ULL },    {   305,   92,  12024538023802026127ULL },
    {   306,   93,   2404907604760405225ULL },    {   307,   93,   4809815209520810451ULL },
    {   308,   93,   9619630419041620901ULL },    {   309,   94,   1923926083808324180ULL },
    {   310,   94,   3847852167616648361ULL },    {   311,   94,   7695704335233296721ULL },
    {   312,   94,  15391408670466593442ULL },    {   313,   95,   3078281734093318688ULL },
    {   314,   95,   6156563468186637377ULL },    {   315,   95,  12313126936373274754ULL },
    {   316,   96,   2462625387274654951ULL },    {   317,   96,   4925250774549309902ULL },
    {   318,   96,   9850501549098619803ULL },    {   319,   97,   1970100309819723961ULL },
    {   320,   97,   3940200619639447921ULL },    {   321,   97,   7880401239278895842ULL },
    {   322,   97,  15760802478557791685ULL },    {   323,   98,   3152160495711558337ULL },
    {   324,   98,   6304320991423116674ULL },    {   325,   98,  12608641982846233348ULL },
    {   326,   99,   2521728396569246670ULL },    {   327,   99,   5043456793138493339ULL },
    {   328,   99,  10086913586276986678ULL },    {   329,  100,   2017382717255397336ULL },
    {   330,  100,   4034765434510794671ULL },    {   331,  100,   8069530869021589343ULL },
    {   332,  100,  16139061738043178685ULL },    {   333,  101,   3227812347608635737ULL },
    {   334,  101,   6455624695217271474ULL },    {   335,  101,  12911249390434542948ULL },
    {   336,  102,   2582249878086908590ULL },    {   337,  102,   5164499756173817179ULL },
    {   338,  102,  10328999512347634359ULL },    {   339,  103,   2065799902469526872ULL },
    {   340,  103,   4131599804939053743ULL },    {   341,  103,   8263199609878107487ULL },
    {   342,  103,  16526399219756214974ULL },    {   343,  104,   3305279843951242995ULL },
    {   344,  104,   6610559687902485990ULL },    {   345,  104,  13221119375804971979ULL },
    {   346,  105,   2644223875160994396ULL },    {   347,  105,   5288447750321988792ULL },
    {   348,  105,  10576895500643977583ULL },    {   349,  106,   2115379100128795517ULL },
    {   350,  106,   4230758200257591033ULL },    {   351,  106,   8461516400515182067ULL },
    {   352,  106,  16923032801030364133ULL },    {   353,  107,   3384606560206072827ULL },
    {   354,  107,   6769213120412145653ULL },    {   355,  107,  13538426240824291307ULL },
    {   356,  108,   2707685248164858261ULL },    {   357,  108,   5415370496329716523ULL },
    {   358,  108,  10830740992659433045ULL },    {   359,  109,   2166148198531886609ULL },
    {   360,  109,   4332296397063773218ULL },    {   361,  109,   8664592794127546436ULL },
    {   362,  109,  17329185588255092872ULL },    {   363,  110,   3465837117651018574ULL },
    {   364,  110,   6931674235302037149ULL },    {   365,  110,  13863348470604074298ULL },
    {   366,  111,   2772669694120814860ULL },    {   367,  111,   5545339388241629719ULL },
    {   368,  111,  11090678776483259438ULL },    {   369,  112,   2218135755296651888ULL },
    {   370,  112,   4436271510593303775ULL },    {   371,  112,   8872543021186607551ULL },
    {   372,  112,  17745086042373215101ULL },    {   373,  113,   3549017208474643020ULL },
    {   374,  113,   7098034416949286041ULL },    {   375,  113,  14196068833898572081ULL },
    {   376,  114,   2839213766779714416ULL },    {   377,  114,   5678427533559428832ULL },
    {   378,  114,  11356855067118857665ULL },    {   379,  115,   2271371013423771533ULL },
    {   380,  115,   4542742026847543066ULL },    {   381,  115,   9085484053695086132ULL },
    {   382,  115,  18170968107390172264ULL },    {   383,  116,   3634193621478034453ULL },
    {   384,  116,   7268387242956068905ULL },    {   385,  116,  14536774485912137811ULL },
    {   386,  117,   2907354897182427562ULL },    {   387,  117,   5814709794364855124ULL },
    {   388,  117,  11629419588729710249ULL },    {   389,  118,   2325883917745942050ULL },
    {   390,  118,   4651767835491884100ULL },    {   391,  118,   9303535670983768199ULL },
    {   392,  119,   1860707134196753640ULL },    {   393,  119,   3721414268393507280ULL },
    {   394,  119,   7442828536787014559ULL },    {   395,  119,  14885657073574029118ULL },
    {   396,  120,   2977131414714805824ULL },    {   397,  120,   5954262829429611647ULL },
    {   398,  120,  11908525658859223295ULL },    {   399,  121,   2381705131771844659ULL },
    {   400,  121,   4763410263543689318ULL },    {   401,  121,   9526820527087378636ULL },
    {   402,  122,   1905364105417475727ULL },    {   403,  122,   3810728210834951454ULL },
    {   404,  122,   7621456421669902909ULL },    {   405,  122,  15242912843339805817ULL },
    {   406,  123,   3048582568667961163ULL },    {   407,  123,   6097165137335922327ULL },
    {   408,  123,  12194330274671844654ULL },    {   409,  124,   2438866054934368931ULL },
    {   410,  124,   4877732109868737862ULL },    {   411,  124,   9755464219737475723ULL },
    {   412,  125,   1951092843947495145ULL },    {   413,  125,   3902185687894990289ULL },
    {   414,  125,   7804371375789980578ULL },    {   415,  125,  15608742751579961157ULL },
    {   416,  126,   3121748550315992231ULL },    {   417,  126,   6243497100631984463ULL },
    {   418,  126,  12486994201263968926ULL },    {   419,  127,   2497398840252793785ULL },
    {   420,  127,   4994797680505587570ULL },    {   421,  127,   9989595361011175140ULL },
    {   422,  128,   1997919072202235028ULL },    {   423,  128,   3995838144404470056ULL },
    {   424,  128,   7991676288808940112ULL },    {   425,  128,  15983352577617880225ULL },
    {   426,  129,   3196670515523576045ULL },    {   427,  129,   6393341031047152090ULL },
    {   428,  129,  12786682062094304180ULL },    {   429,  130,   2557336412418860836ULL },
    {   430,  130,   5114672824837721672ULL },    {   431,  130,  10229345649675443344ULL },
    {   432,  131,   2045869129935088669ULL },    {   433,  131,   4091738259870177338ULL },
    {   434,  131,   8183476519740354675ULL },    {   435,  131,  16366953039480709350ULL },
    {   436,  132,   3273390607896141870ULL },    {   437,  132,   6546781215792283740ULL },
    {   438,  132,  13093562431584567480ULL },    {   439,  133,   2618712486316913496ULL },
    {   440,  133,   5237424972633826992ULL },    {   441,  133,  10474849945267653984ULL },
    {   442,  134,   2094969989053530797ULL },    {   443,  134,   4189939978107061594ULL },
    {   444,  134,   8379879956214123187ULL },    {   445,  134,  16759759912428246374ULL },
    {   446,  135,   3351951982485649275ULL },    {   447,  135,   6703903964971298550ULL },
    {   448,  135,  13407807929942597100ULL },    {   449,  136,   2681561585988519420ULL },
    {   450,  136,   5363123171977038840ULL },    {   451,  136,  10726246343954077680ULL },
    {   452,  137,   2145249268790815536ULL },    {   453,  137,   4290498537581631072ULL },
    {   454,  137,   8580997075163262144ULL },    {   455,  137,  17161994150326524287ULL },
    {   456,  138,   3432398830065304857ULL },    {   457,  138,   6864797660130609715ULL },
    {   458,  138,  13729595320261219430ULL },    {   459,  139,   2745919064052243886ULL },
    {   460,  139,   5491838128104487772ULL },    {   461,  139,  10983676256208975544ULL },
    {   462,  140,   2196735251241795109ULL },    {   463,  140,   4393470502483590218ULL },
    {   464,  140,   8786941004967180435ULL },    {   465,  140,  17573882009934360870ULL },
    {   466,  141,   3514776401986872174ULL },    {   467,  141,   7029552803973744348ULL },
    {   468,  141,  14059105607947488696ULL },    {   469,  142,   2811821121589497739ULL },
    {   470,  142,   5623642243178995479ULL },    {   471,  142,  11247284486357990957ULL },
    {   472,  143,   2249456897271598191ULL },    {   473,  143,   4498913794543196383ULL },
    {   474,  143,   8997827589086392766ULL },    {   475,  143,  17995655178172785531ULL },
    {   476,  144,   3599131035634557106ULL },    {   477,  144,   7198262071269114212ULL },
    {   478,  144,  14396524142538228425ULL },    {   479,  145,   2879304828507645685ULL },
    {   480,  145,   5758609657015291370ULL },    {   481,  145,  11517219314030582740ULL },
    {   482,  146,   2303443862806116548ULL },    {   483,  146,   4606887725612233096ULL },
    {   484,  146,   9213775451224466192ULL },    {   485,  146,  18427550902448932384ULL },
    {   486,  147,   3685510180489786477ULL },    {   487,  147,   7371020360979572954ULL },
    {   488,  147,  14742040721959145907ULL },    {   489,  148,   2948408144391829181ULL },
    {   490,  148,   5896816288783658363ULL },    {   491,  148,  11793632577567316726ULL },
    {   492,  149,   2358726515513463345ULL },    {   493,  149,   4717453031026926690ULL },
    {   494,  149,   9434906062053853381ULL },    {   495,  150,   1886981212410770676ULL },
    {   496,  150,   3773962424821541352ULL },    {   497,  150,   7547924849643082704ULL },
    {   498,  150,  15095849699286165409ULL },    {   499,  151,   3019169939857233082ULL },
    {   500,  151,   6038339879714466164ULL },    {   501,  151,  12076679759428932327ULL },
    {   502,  152,   2415335951885786465ULL },    {   503,  152,   4830671903771572931ULL },
    {   504,  152,   9661343807543145862ULL },    {   505,  153,   1932268761508629172ULL },
    {   506,  153,   3864537523017258345ULL },    {   507,  153,   7729075046034516689ULL },
    {   508,  153,  15458150092069033379ULL },    {   509,  154,   3091630018413806676ULL },
    {   510,  154,   6183260036827613352ULL },    {   511,  154,  12366520073655226703ULL },
    {   512,  155,   2473304014731045341ULL },    {   513,  155,   4946608029462090681ULL },
    {   514,  155,   9893216058924181362ULL },    {   515,  156,   1978643211784836272ULL },
    {   516,  156,   3957286423569672545ULL },    {   517,  156,   7914572847139345090ULL },
    {   518,  156,  15829145694278690180ULL },    {   519,  157,   3165829138855738036ULL },
    {   520,  157,   6331658277711476072ULL },    {   521,  157,  12663316555422952144ULL },
    {   522,  158,   2532663311084590429ULL },    {   523,  158,   5065326622169180858ULL },
    {   524,  158,  10130653244338361715ULL },    {   525,  159,   2026130648867672343ULL },
    {   526,  159,   4052261297735344686ULL },    {   527,  159,   8104522595470689372ULL },
    {   528,  159,  16209045190941378744ULL },    {   529,  160,   3241809038188275749ULL },
    {   530,  160,   6483618076376551498ULL },    {   531,  160,  12967236152753102995ULL },
    {   532,  161,   2593447230550620599ULL },    {   533,  161,   5186894461101241198ULL },
    {   534,  161,  10373788922202482396ULL },    {   535,  162,   2074757784440496479ULL },
    {   536,  162,   4149515568880992959ULL },    {   537,  162,   8299031137761985917ULL },
    {   538,  162,  16598062275523971834ULL },    {   539,  163,   3319612455104794367ULL },
    {   540,  163,   6639224910209588734ULL },    {   541,  163,  13278449820419177467ULL },
    {   542,  164,   2655689964083835493ULL },    {   543,  164,   5311379928167670987ULL },
    {   544,  164,  10622759856335341974ULL },    {   545,  165,   2124551971267068395ULL },
    {   546,  165,   4249103942534136790ULL },    {   547,  165,   8498207885068273579ULL },
    {   548,  165,  16996415770136547158ULL },    {   549,  166,   3399283154027309432ULL },
    {   550,  166,   6798566308054618863ULL },    {   551,  166,  13597132616109237726ULL },
    {   552,  167,   2719426523221847545ULL },    {   553,  167,   5438853046443695091ULL },
    {   554,  167,  10877706092887390181ULL },    {   555,  168,   2175541218577478036ULL },
    {   556,  168,   4351082437154956072ULL },    {   557,  168,   8702164874309912145ULL },
    {   558,  168,  17404329748619824290ULL },    {   559,  169,   3480865949723964858ULL },
    {   560,  169,   6961731899447929716ULL },    {   561,  169,  13923463798895859432ULL },
    {   562,  170,   2784692759779171886ULL },    {   563,  170,   5569385519558343773ULL },
    {   564,  170,  11138771039116687546ULL },    {   565,  171,   2227754207823337509ULL },
    {   566,  171,   4455508415646675018ULL },    {   567,  171,   8911016831293350036ULL },
    {   568,  171,  17822033662586700073ULL },    {   569,  172,   3564406732517340015ULL },
    {   570,  172,   7128813465034680029ULL },    {   571,  172,  14257626930069360058ULL },
    {   572,  173,   2851525386013872012ULL },    {   573,  173,   5703050772027744023ULL },
    {   574,  173,  11406101544055488047ULL },    {   575,  174,   2281220308811097609ULL },
    {   576,  174,   4562440617622195219ULL },    {   577,  174,   9124881235244390437ULL },
    {   578,  174,  18249762470488780875ULL },    {   579,  175,   3649952494097756175ULL },
    {   580,  175,   7299904988195512350ULL },    {   581,  175,  14599809976391024700ULL },
    {   582,  176,   2919961995278204940ULL },    {   583,  176,   5839923990556409880ULL },
    {   584,  176,  11679847981112819760ULL },    {   585,  177,   2335969596222563952ULL },
    {   586,  177,   4671939192445127904ULL },    {   587,  177,   9343878384890255808ULL },
    {   588,  178,   1868775676978051162ULL },    {   589,  178,   3737551353956102323ULL },
    {   590,  178,   7475102707912204646ULL },    {   591,  178,  14950205415824409292ULL },
    {   592,  179,   2990041083164881858ULL },    {   593,  179,   5980082166329763717ULL },
    {   594,  179,  11960164332659527434ULL },    {   595,  180,   2392032866531905487ULL },
    {   596,  180,   4784065733063810974ULL },    {   597,  180,   9568131466127621947ULL },
    {   598,  181,   1913626293225524389ULL },    {   599,  181,   3827252586451048779ULL },
    {   600,  181,   7654505172902097558ULL },    {   601,  181,  15309010345804195115ULL },
    {   602,  182,   3061802069160839023ULL },    {   603,  182,   6123604138321678046ULL },
    {   604,  182,  12247208276643356092ULL },    {   605,  183,   2449441655328671218ULL },
    {   606,  183,   4898883310657342437ULL },    {   607,  183,   9797766621314684874ULL },
    {   608,  184,   1959553324262936975ULL },    {   609,  184,   3919106648525873950ULL },
    {   610,  184,   7838213297051747899ULL },    {   611,  184,  15676426594103495798ULL },
    {   612,  185,   3135285318820699160ULL },    {   613,  185,   6270570637641398319ULL },
    {   614,  185,  12541141275282796639ULL },    {   615,  186,   2508228255056559328ULL },
    {   616,  186,   5016456510113118655ULL },    {   617,  186,  10032913020226237311ULL },
    {   618,  187,   2006582604045247462ULL },    {   619,  187,   4013165208090494924ULL },
    {   620,  187,   8026330416180989849ULL },    {   621,  187,  16052660832361979697ULL },
    {   622,  188,   3210532166472395939ULL },    {   623,  188,   6421064332944791879ULL },
    {   624,  188,  12842128665889583758ULL },    {   625,  189,   2568425733177916752ULL },
    {   626,  189,   5136851466355833503ULL },    {   627,  189,  10273702932711667006ULL },
    {   628,  190,   2054740586542333401ULL },    {   629,  190,   4109481173084666803ULL },
    {   630,  190,   8218962346169333605ULL },    {   631,  190,  16437924692338667210ULL },
    {   632,  191,   3287584938467733442ULL },    {   633,  191,   6575169876935466884ULL },
    {   634,  191,  13150339753870933768ULL },    {   635,  192,   2630067950774186754ULL },
    {   636,  192,   5260135901548373507ULL },    {   637,  192,  10520271803096747014ULL },
    {   638,  193,   2104054360619349403ULL },    {   639,  193,   4208108721238698806ULL },
    {   640,  193,   8416217442477397612ULL },    {   641,  193,  16832434884954795223ULL },
    {   642,  194,   3366486976990959045ULL },    {   643,  194,   6732973953981918089ULL },
    {   644,  194,  13465947907963836179ULL },    {   645,  195,   2693189581592767236ULL },
    {   646,  195,   5386379163185534471ULL },    {   647,  195,  10772758326371068943ULL },
    {   648,  196,   2154551665274213789ULL },    {   649,  196,   4309103330548427577ULL },
    {   650,  196,   8618206661096855154ULL },    {   651,  196,  17236413322193710309ULL },
    {   652,  197,   3447282664438742062ULL },    {   653,  197,   6894565328877484123ULL },
    {   654,  197,  13789130657754968247ULL },    {   655,  198,   2757826131550993649ULL },
    {   656,  198,   5515652263101987299ULL },    {   657,  198,  11031304526203974597ULL },
    {   658,  199,   2206260905240794919ULL },    {   659,  199,   4412521810481589839ULL },
    {   660,  199,   8825043620963179678ULL },    {   661,  199,  17650087241926359356ULL },
    {   662,  200,   3530017448385271871ULL },    {   663,  200,   7060034896770543742ULL },
    {   664,  200,  14120069793541087485ULL },    {   665,  201,   2824013958708217497ULL },
    {   666,  201,   5648027917416434994ULL },    {   667,  201,  11296055834832869988ULL },
    {   668,  202,   2259211166966573998ULL },    {   669,  202,   4518422333933147995ULL },
    {   670,  202,   9036844667866295990ULL },    {   671,  202,  18073689335732591980ULL },
    {   672,  203,   3614737867146518396ULL },    {   673,  203,   7229475734293036792ULL },
    {   674,  203,  14458951468586073584ULL },    {   675,  204,   2891790293717214717ULL },
    {   676,  204,   5783580587434429434ULL },    {   677,  204,  11567161174868858868ULL },
    {   678,  205,   2313432234973771774ULL },    {   679,  205,   4626864469947543547ULL },
    {   680,  205,   9253728939895087094ULL },    {   681,  206,   1850745787979017419ULL },
    {   682,  206,   3701491575958034838ULL },    {   683,  206,   7402983151916069675ULL },
    {   684,  206,  14805966303832139350ULL },    {   685,  207,   2961193260766427870ULL },
    {   686,  207,   5922386521532855740ULL },    {   687,  207,  11844773043065711480ULL },
    {   688,  208,   2368954608613142296ULL },    {   689,  208,   4737909217226284592ULL },
    {   690,  208,   9475818434452569184ULL },    {   691,  209,   1895163686890513837ULL },
    {   692,  209,   3790327373781027674ULL },    {   693,  209,   7580654747562055347ULL },
    {   694,  209,  15161309495124110695ULL },    {   695,  210,   3032261899024822139ULL },
    {   696,  210,   6064523798049644278ULL },    {   697,  210,  12129047596099288556ULL },
    {   698,  211,   2425809519219857711ULL },    {   699,  211,   4851619038439715422ULL },
    {   700,  211,   9703238076879430845ULL },    {   701,  212,   1940647615375886169ULL },
    {   702,  212,   3881295230751772338ULL },    {   703,  212,   7762590461503544676ULL },
    {   704,  212,  15525180923007089351ULL },    {   705,  213,   3105036184601417870ULL },
    {   706,  213,   6210072369202835741ULL },    {   707,  213,  12420144738405671481ULL },
    {   708,  214,   2484028947681134296ULL },    {   709,  214,   4968057895362268592ULL },
    {   710,  214,   9936115790724537185ULL },    {   711,  215,   1987223158144907437ULL },
    {   712,  215,   3974446316289814874ULL },    {   713,  215,   7948892632579629748ULL },
    {   714,  215,  15897785265159259496ULL },    {   715,  216,   3179557053031851899ULL },
    {   716,  216,   6359114106063703798ULL },    {   717,  216,  12718228212127407597ULL },
    {   718,  217,   2543645642425481519ULL },    {   719,  217,   5087291284850963039ULL },
    {   720,  217,  10174582569701926077ULL },    {   721,  218,   2034916513940385215ULL },
    {   722,  218,   4069833027880770431ULL },    {   723,  218,   8139666055761540862ULL },
    {   724,  218,  16279332111523081724ULL },    {   725,  219,   3255866422304616345ULL },
    {   726,  219,   6511732844609232690ULL },    {   727,  219,  13023465689218465379ULL },
    {   728,  220,   2604693137843693076ULL },    {   729,  220,   5209386275687386152ULL },
    {   730,  220,  10418772551374772303ULL },    {   731,  221,   2083754510274954461ULL },
    {   732,  221,   4167509020549908921ULL },    {   733,  221,   8335018041099817843ULL },
    {   734,  221,  16670036082199635685ULL },    {   735,  222,   3334007216439927137ULL },
    {   736,  222,   6668014432879854274ULL },    {   737,  222,  13336028865759708548ULL },
    {   738,  223,   2667205773151941710ULL },    {   739,  223,   5334411546303883419ULL },
    {   740,  223,  10668823092607766839ULL },    {   741,  224,   2133764618521553368ULL },
    {   742,  224,   4267529237043106735ULL },    {   743,  224,   8535058474086213471ULL },
    {   744,  224,  17070116948172426942ULL },    {   745,  225,   3414023389634485388ULL },
    {   746,  225,   6828046779268970777ULL },    {   747,  225,  13656093558537941553ULL },
    {   748,  226,   2731218711707588311ULL },    {   749,  226,   5462437423415176621ULL },
    {   750,  226,  10924874846830353243ULL },    {   751,  227,   2184974969366070649ULL },
    {   752,  227,   4369949938732141297ULL },    {   753,  227,   8739899877464282594ULL },
    {   754,  227,  17479799754928565188ULL },    {   755,  228,   3495959950985713038ULL },
    {   756,  228,   6991919901971426075ULL },    {   757,  228,  13983839803942852151ULL },
    {   758,  229,   2796767960788570430ULL },    {   759,  229,   5593535921577140860ULL },
    {   760,  229,  11187071843154281720ULL },    {   761,  230,   2237414368630856344ULL },
    {   762,  230,   4474828737261712688ULL },    {   763,  230,   8949657474523425376ULL },
    {   764,  230,  17899314949046850753ULL },    {   765,  231,   3579862989809370151ULL },
    {   766,  231,   7159725979618740301ULL },    {   767,  231,  14319451959237480602ULL },
    {   768,  232,   2863890391847496120ULL },    {   769,  232,   5727780783694992241ULL },
    {   770,  232,  11455561567389984482ULL },    {   771,  233,   2291112313477996896ULL },
    {   772,  233,   4582224626955993793ULL },    {   773,  233,   9164449253911987585ULL },
    {   774,  233,  18328898507823975171ULL },    {   775,  234,   3665779701564795034ULL },
    {   776,  234,   7331559403129590068ULL },    {   777,  234,  14663118806259180137ULL },
    {   778,  235,   2932623761251836027ULL },    {   779,  235,   5865247522503672055ULL },
    {   780,  235,  11730495045007344109ULL },    {   781,  236,   2346099009001468822ULL },
    {   782,  236,   4692198018002937644ULL },    {   783,  236,   9384396036005875287ULL },
    {   784,  237,   1876879207201175057ULL },    {   785,  237,   3753758414402350115ULL },
    {   786,  237,   7507516828804700230ULL },    {   787,  237,  15015033657609400460ULL },
    {   788,  238,   3003006731521880092ULL },    {   789,  238,   6006013463043760184ULL },
    {   790,  238,  12012026926087520368ULL },    {   791,  239,   2402405385217504074ULL },
    {   792,  239,   4804810770435008147ULL },    {   793,  239,   9609621540870016294ULL },
    {   794,  240,   1921924308174003259ULL },    {   795,  240,   3843848616348006518ULL },
    {   796,  240,   7687697232696013035ULL },    {   797,  240,  15375394465392026071ULL },
    {   798,  241,   3075078893078405214ULL },    {   799,  241,   6150157786156810428ULL },
    {   800,  241,  12300315572313620857ULL },    {   801,  242,   2460063114462724171ULL },
    {   802,  242,   4920126228925448343ULL },    {   803,  242,   9840252457850896685ULL },
    {   804,  243,   1968050491570179337ULL },    {   805,  243,   3936100983140358674ULL },
    {   806,  243,   7872201966280717348ULL },    {   807,  243,  15744403932561434697ULL },
    {   808,  244,   3148880786512286939ULL },    {   809,  244,   6297761573024573879ULL },
    {   810,  244,  12595523146049147757ULL },    {   811,  245,   2519104629209829551ULL },
    {   812,  245,   5038209258419659103ULL },    {   813,  245,  10076418516839318206ULL },
    {   814,  246,   2015283703367863641ULL },    {   815,  246,   4030567406735727282ULL },
    {   816,  246,   8061134813471454565ULL },    {   817,  246,  16122269626942909129ULL },
    {   818,  247,   3224453925388581826ULL },    {   819,  247,   6448907850777163652ULL },
    {   820,  247,  12897815701554327304ULL },    {   821,  248,   2579563140310865461ULL },
    {   822,  248,   5159126280621730921ULL },    {   823,  248,  10318252561243461843ULL },
    {   824,  249,   2063650512248692369ULL },    {   825,  249,   4127301024497384737ULL },
    {   826,  249,   8254602048994769474ULL },    {   827,  249,  16509204097989538949ULL },
    {   828,  250,   3301840819597907790ULL },    {   829,  250,   6603681639195815579ULL },
    {   830,  250,  13207363278391631159ULL },    {   831,  251,   2641472655678326232ULL },
    {   832,  251,   5282945311356652464ULL },    {   833,  251,  10565890622713304927ULL },
    {   834,  252,   2113178124542660985ULL },    {   835,  252,   4226356249085321971ULL },
    {   836,  252,   8452712498170643942ULL },    {   837,  252,  16905424996341287883ULL },
    {   838,  253,   3381084999268257577ULL },    {   839,  253,   6762169998536515153ULL },
    {   840,  253,  13524339997073030307ULL },    {   841,  254,   2704867999414606061ULL },
    {   842,  254,   5409735998829212123ULL },    {   843,  254,  10819471997658424245ULL },
    {   844,  255,   2163894399531684849ULL },    {   845,  255,   4327788799063369698ULL },
    {   846,  255,   8655577598126739396ULL },    {   847,  255,  17311155196253478792ULL },
    {   848,  256,   3462231039250695758ULL },    {   849,  256,   6924462078501391517ULL },
    {   850,  256,  13848924157002783034ULL },    {   851,  257,   2769784831400556607ULL },
    {   852,  257,   5539569662801113214ULL },    {   853,  257,  11079139325602226427ULL },
    {   854,  258,   2215827865120445285ULL },    {   855,  258,   4431655730240890571ULL },
    {   856,  258,   8863311460481781142ULL },    {   857,  258,  17726622920963562283ULL },
    {   858,  259,   3545324584192712457ULL },    {   859,  259,   7090649168385424913ULL },
    {   860,  259,  14181298336770849827ULL },    {   861,  260,   2836259667354169965ULL },
    {   862,  260,   5672519334708339931ULL },    {   863,  260,  11345038669416679861ULL },
    {   864,  261,   2269007733883335972ULL },    {   865,  261,   4538015467766671945ULL },
    {   866,  261,   9076030935533343889ULL },    {   867,  261,  18152061871066687778ULL },
    {   868,  262,   3630412374213337556ULL },    {   869,  262,   7260824748426675111ULL },
    {   870,  262,  14521649496853350223ULL },    {   871,  263,   2904329899370670045ULL },
    {   872,  263,   5808659798741340089ULL },    {   873,  263,  11617319597482680178ULL },
    {   874,  264,   2323463919496536036ULL },    {   875,  264,   4646927838993072071ULL },
    {   876,  264,   9293855677986144142ULL },    {   877,  265,   1858771135597228828ULL },
    {   878,  265,   3717542271194457657ULL },    {   879,  265,   7435084542388915314ULL },
    {   880,  265,  14870169084777830628ULL },    {   881,  266,   2974033816955566126ULL },
    {   882,  266,   5948067633911132251ULL },    {   883,  266,  11896135267822264502ULL },
    {   884,  267,   2379227053564452900ULL },    {   885,  267,   4758454107128905801ULL },
    {   886,  267,   9516908214257811602ULL },    {   887,  268,   1903381642851562320ULL },
    {   888,  268,   3806763285703124641ULL },    {   889,  268,   7613526571406249282ULL },
    {   890,  268,  15227053142812498563ULL },    {   891,  269,   3045410628562499713ULL },
    {   892,  269,   6090821257124999425ULL },    {   893,  269,  12181642514249998850ULL },
    {   894,  270,   2436328502849999770ULL },    {   895,  270,   4872657005699999540ULL },
    {   896,  270,   9745314011399999080ULL },    {   897,  271,   1949062802279999816ULL },
    {   898,  271,   3898125604559999632ULL },    {   899,  271,   7796251209119999264ULL },
    {   900,  271,  15592502418239998529ULL },    {   901,  272,   3118500483647999706ULL },
    {   902,  272,   6237000967295999411ULL },    {   903,  272,  12474001934591998823ULL },
    {   904,  273,   2494800386918399765ULL },    {   905,  273,   4989600773836799529ULL },
    {   906,  273,   9979201547673599058ULL },    {   907,  274,   1995840309534719812ULL },
    {   908,  274,   3991680619069439623ULL },    {   909,  274,   7983361238138879247ULL },
    {   910,  274,  15966722476277758493ULL },    {   911,  275,   3193344495255551699ULL },
    {   912,  275,   6386688990511103397ULL },    {   913,  275,  12773377981022206795ULL },
    {   914,  276,   2554675596204441359ULL },    {   915,  276,   5109351192408882718ULL },
    {   916,  276,  10218702384817765436ULL },    {   917,  277,   2043740476963553087ULL },
    {   918,  277,   4087480953927106174ULL },    {   919,  277,   8174961907854212349ULL },
    {   920,  277,  16349923815708424697ULL },    {   921,  278,   3269984763141684939ULL },
    {   922,  278,   6539969526283369879ULL },    {   923,  278,  13079939052566739758ULL },
    {   924,  279,   2615987810513347952ULL },    {   925,  279,   5231975621026695903ULL },
    {   926,  279,  10463951242053391806ULL },    {   927,  280,   2092790248410678361ULL },
    {   928,  280,   4185580496821356722ULL },    {   929,  280,   8371160993642713445ULL },
    {   930,  280,  16742321987285426890ULL },    {   931,  281,   3348464397457085378ULL },
    {   932,  281,   6696928794914170756ULL },    {   933,  281,  13393857589828341512ULL },
    {   934,  282,   2678771517965668302ULL },    {   935,  282,   5357543035931336605ULL },
    {   936,  282,  10715086071862673209ULL },    {   937,  283,   2143017214372534642ULL },
    {   938,  283,   4286034428745069284ULL },    {   939,  283,   8572068857490138568ULL },
    {   940,  283,  17144137714980277135ULL },    {   941,  284,   3428827542996055427ULL },
    {   942,  284,   6857655085992110854ULL },    {   943,  284,  13715310171984221708ULL },
    {   944,  285,   2743062034396844342ULL },    {   945,  285,   5486124068793688683ULL },
    {   946,  285,  10972248137587377367ULL },    {   947,  286,   2194449627517475473ULL },
    {   948,  286,   4388899255034950947ULL },    {   949,  286,   8777798510069901893ULL },
    {   950,  286,  17555597020139803786ULL },    {   951,  287,   3511119404027960757ULL },
    {   952,  287,   7022238808055921515ULL },    {   953,  287,  14044477616111843029ULL },
    {   954,  288,   2808895523222368606ULL },    {   955,  288,   5617791046444737212ULL },
    {   956,  288,  11235582092889474423ULL },    {   957,  289,   2247116418577894885ULL },
    {   958,  289,   4494232837155789769ULL },    {   959,  289,   8988465674311579539ULL },
    {   960,  289,  17976931348623159077ULL },    {   961,  290,   3595386269724631815ULL },
    {   962,  290,   7190772539449263631ULL },    {   963,  290,  14381545078898527262ULL }
};

//=====================================================================================================
//
// FUNCTIONS
//

/**
 *
 *  Multiply two 64-bit unsigned integers and produce 128-bit result
 *
 *  (u * v) -> w
 *
 *  Element w[0] of two-element array w always holds 64 least significant bits of result,
 *  even on big endian machines.
 *
 */
static inline void  multiply_128(
    uint64_t   u,
    uint64_t   v,
    uint64_t*  w
)
{
    // Make use of 64x64->128 unsigned multiplication instruction
    // (if processor has this instruction and compiler allows for using it).
#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__) && (__SIZEOF_INT128__ == 16)
    unsigned __int128  value_w = ((unsigned __int128)u) * v;
    w[0] = ((uint64_t)( value_w       ));
    w[1] = ((uint64_t)( value_w >> 64 ));
#elif defined(_MSC_VER) && defined(_M_X64)
    w[0] = _umul128( u, v, w + 1 );
#else
    // On other processors and compilers, do column multiplication.
    uint64_t  u1 = u >> 32;   uint64_t  u0 = u & 0xFFFFFFFFULL;
    uint64_t  v1 = v >> 32;   uint64_t  v0 = v & 0xFFFFFFFFULL;

    uint64_t  t  = u0 * v0;
    uint64_t  w0 = t & 0xFFFFFFFFULL;
    uint64_t  k  = t >> 32;
    t            = u1 * v0 + k;

    uint64_t  w1 = t & 0xFFFFFFFFULL;
    uint64_t  w2 = t >> 32;
    t            = u0 * v1 + w1;
    k            = t >> 32;

    w[0] = (t << 32) + w0;
    w[1] = u1 * v1 + w2 + k;
#endif
}

/**
 *
 *  Count the number of leading zero bits in provided 64-bit unsigned integer
 *
 *  Behavior of this function is undefined if a == 0.
 *
 */
static inline unsigned int  count_leading_zeros( uint64_t  a )
{
    // Make use of 64-bit leading zero count instruction
    // (if processor has this instruction and compiler allows for using it).
#if defined(__GNUC__) || defined(__clang__)
    return  __builtin_clzll( a );
#elif defined(_MSC_VER) && defined(_M_X64)
    unsigned long  most_significant_bit_number = 0;
    _BitScanReverse64( &most_significant_bit_number, a );
    return  63 - most_significant_bit_number;
#elif defined(_MSC_VER) && (!defined(_M_X64))
    if( a <= 0xFFFFFFFFULL )
    {
        unsigned long  most_significant_bit_number = 0;
        _BitScanReverse( &most_significant_bit_number, (uint32_t)a );
        return  63 - most_significant_bit_number;
    }
    else
    {
        unsigned long  most_significant_bit_number = 0;
        _BitScanReverse( &most_significant_bit_number, (uint32_t)(a >> 32) );
        return  31 - most_significant_bit_number;
    }
#else
    // On other processors and compilers, count leading zero bits manually
    unsigned int  n = 0;
    if( a <= 0x00000000FFFFFFFFULL ) { n += 32; a <<= 32; }
    if( a <= 0x0000FFFFFFFFFFFFULL ) { n += 16; a <<= 16; }
    if( a <= 0x00FFFFFFFFFFFFFFULL ) { n += 8;  a <<= 8;  }
    if( a <= 0x0FFFFFFFFFFFFFFFULL ) { n += 4;  a <<= 4;  }
    if( a <= 0x3FFFFFFFFFFFFFFFULL ) { n += 2;  a <<= 2;  }
    if( a <= 0x7FFFFFFFFFFFFFFFULL ) { n += 1;            }
    return  n;
#endif
}

/**
 *
 *  Convert extended-precision decimal to double-precision binary
 *  (mantissa is rounded to nearest representable value)
 *
 *  (a * 10^b) -> (c * 2^d)
 *
 *  a != 0. Decimal point is on the right side of the input mantissa a.
 *
 *  Resulting binary mantissa c is rounded to 53 bits (as in IEEE 754 double-precision binary).
 *  If remainder >= 0.5, then mantissa is rounded up, otherwise it's rounded down.
 *
 *  On exit from this function, binary point is located after first bit of mantissa,
 *  which is always equal to 1 (binary exponent is adjusted accordingly).
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Invalid argument or internal error.
 *
 */
static int  convert_extended_decimal_to_binary_and_round(
    uint64_t   a,
    int32_t    b,
    uint64_t*  c,
    int32_t*   d
)
{
    // 1. Check input arguments
    if(( a == 0 )||
       ( b < powers_of_ten_[0].decimal_exponent )||
       ( b > powers_of_ten_[sizeof(powers_of_ten_)/sizeof(powers_of_ten_[0]) - 1].decimal_exponent ))
        return  0;

    // 2. Convert (a * 10^b) -> (mantissa * 2^exponent)
    uint64_t  mantissa = powers_of_ten_[ b - powers_of_ten_[0].decimal_exponent ].binary_mantissa;
    int32_t   exponent = powers_of_ten_[ b - powers_of_ten_[0].decimal_exponent ].binary_exponent;
    uint64_t  long_mantissa[2];
    multiply_128( a, mantissa, long_mantissa );
    if( long_mantissa[1] != 0 )   // high half
    {
        unsigned int  lz = count_leading_zeros( long_mantissa[1] );
        if( lz == 0 )
            mantissa = long_mantissa[1];
        else
            mantissa = ( long_mantissa[1] << lz )|( long_mantissa[0] >> (64 - lz) );
        exponent += (64 - lz);
    }
    else if( long_mantissa[0] != 0 )   // low half
    {
        unsigned int  lz = count_leading_zeros( long_mantissa[0] );
        mantissa = ( long_mantissa[0] << lz );
        exponent -= lz;
    }
    else
        return  0;   // product is unexpectedly zero

    // 3. Round mantissa
    uint64_t  remainder = mantissa & 0x07FFULL;  // 0x07FF: 11 least significant bits set, where 11 = 64-53
    if( remainder < 0x0400ULL )
        mantissa -= remainder;
    else
    {
        mantissa += (0x0800ULL - remainder);
        if( mantissa == 0 )
        {
            // handle overflow of the mantissa
            mantissa = (1ULL << 63);
            ++exponent;
        }
    }

    // 4. Move binary point 63 bits to the left: adjust exponent
    exponent += 63;

    // 5. Save computation results and exit
    (*c) = mantissa;
    (*d) = exponent;
    return  1;
}

/**
 *
 *  Determine if extended-precision decimal rounds to given double-precision binary with 53-bit mantissa
 *
 *                                                             rounding
 *  @returns  1  if there's a match in conversion  (a * 10^b) ----------> (expected_c * 2^expected_d)
 *
 *  @returns  0  if there's no match or computation error
 *
 */
static int  does_extended_decimal_round_to_given_binary(
    uint64_t   a,
    int32_t    b,
    uint64_t   expected_c,
    int32_t    expected_d
)
{
    // 1. Check/normalize binary (expected_c * 2^expected_d)
    if( expected_c == 0 )
        return  0;
    unsigned int  lz = count_leading_zeros( expected_c );
    expected_c <<= lz;
    expected_d  -= lz;

    // 2. Convert (a * 10^b) to binary with rounding to 53 bits (in round-to-nearest mode)
    uint64_t  actual_c = 0;
    int32_t   actual_d = 0;
    if(! convert_extended_decimal_to_binary_and_round( a, b, &actual_c, &actual_d ) )
        return  0;

    // 3. Compare and compute result of this function
    return(( actual_c == expected_c )&&( actual_d == expected_d ));
}

/**
 *
 *  Convert extended-precision binary to extended-precision decimal (first approximation)
 *
 *  (a * 2^b) -> (c * 10^d)
 *
 *  a != 0. Binary point is after the most significant bit of the input mantissa a.
 *
 *  Resulting decimal mantissa is in the range 10^18 <= c < 10^19.
 *  Decimal point is on the right side of resulting decimal mantissa c.
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Invalid argument or internal error.
 *
 */
static int  convert_binary_to_decimal_1st_approx(
    uint64_t   a,
    int32_t    b,
    uint64_t*  c,
    int32_t*   d
)
{
    // 1. Check/normalize input mantissa.
    if( a == 0 )
        return  0;
    unsigned int  lz = count_leading_zeros( a );
    a <<= lz;
    b  -= lz;

    // 2. Move binary point to the right side of mantissa.
    //    Do bounds check of the input exponent.
    b -= 63;
    if(( b < powers_of_two_[0].binary_exponent )||
       ( b > powers_of_two_[sizeof(powers_of_two_)/sizeof(powers_of_two_[0]) - 1].binary_exponent ))
        return  0;

    // 3. Convert (a * 2^b) -> (long_mantissa * 10^exponent)
    uint64_t  mantissa = powers_of_two_[ b - powers_of_two_[0].binary_exponent ].decimal_mantissa;
    int32_t   exponent = powers_of_two_[ b - powers_of_two_[0].binary_exponent ].decimal_exponent;
    uint64_t  long_mantissa[2];
    multiply_128( a, mantissa, long_mantissa );
        // invariant: 2^63*(0.1*2^64) < long_mantissa < 2^64*(1*2^64)
    mantissa = long_mantissa[1];
        // invariant: 2^63*0.1 < mantissa < 2^64

    // 4. Force resulting decimal mantissa into the range 10^18 <= c < 10^19.
    if( mantissa < POW10_18 )
    {
        mantissa *= 10ULL;
        multiply_128( 10ULL, long_mantissa[0], long_mantissa );
        mantissa += long_mantissa[1];
        --exponent;
    }
    else if( mantissa >= (10ULL * POW10_18) )
    {
        mantissa /= 10ULL;
        ++exponent;
    }

    // 5. Save computation results and exit
    (*c) = mantissa;
    (*d) = exponent;
    return  1;
}

/**
 *
 *  Convert double-precision binary to extended-precision decimal
 *
 *  (a * 2^b) -> (c * 10^d)
 *
 *  a != 0. Binary point is after the most significant bit of the input mantissa a.
 *
 *  Advantages of this function over convert_binary_to_decimal_1st_approx():
 *  - this function works with inexact 53-bit mantissa,
 *    result of bit uncompression of IEEE 754 double precision binary
 *  - this function aims to provide minimal length of decimal representation
 *    by zeroing out decimal digits known to be computed inexactly.
 *
 *  Resulting decimal mantissa is in the range 10^18 <= c < 10^19.
 *  Decimal point is on the right side of resulting decimal mantissa c.
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Invalid argument or internal error.
 *
 */
static int  convert_binary_to_extended_decimal(
    uint64_t   a,
    int32_t    b,
    uint64_t*  c,
    int32_t*   d
)
{
    // 1. Check input parameters and convert binary mantissa in such way that
    //    its most significant bits are 01. Zero out least significant bits of
    //    mantissa, which are not representable in IEEE 754 double precision format.
    if( a == 0 )
        return  0;
    unsigned int  lz = count_leading_zeros( a );
    a <<= lz;
    a >>= 1;
    b   = b - lz + 1;
    a &= (~0x03FFULL);    // 2 msb const `01' + 52 bits of mantissa + 10 lsb zeroed out = 64 bits total

    // 2. Compute first approximation for (a * 2^b), also for ((a-1) * 2^b) and ((a+1) * 2^b).
    //    Reduce all of them to the common exponent (base_d).
    uint64_t  prev_c = 0;  int32_t  prev_d = 0;
    uint64_t  base_c = 0;  int32_t  base_d = 0;
    uint64_t  next_c = 0;  int32_t  next_d = 0;
    if((! convert_binary_to_decimal_1st_approx( a - 0x0400ULL, b, &prev_c, &prev_d ) )||
       (! convert_binary_to_decimal_1st_approx( a            , b, &base_c, &base_d ) )||
       (! convert_binary_to_decimal_1st_approx( a + 0x0400ULL, b, &next_c, &next_d ) ))
        return  0;
    if( prev_d < next_d )
    {
        prev_c /= 10ULL;
        ++prev_d;
    }
    if( base_d < next_d )
    {
        base_c /= 10ULL;
        ++base_d;
    }

    // 3. Check invariants before starting the binary search
    if(( prev_c >= base_c )||( base_c >= next_c )||
       (! does_extended_decimal_round_to_given_binary( prev_c, prev_d, a - 0x0400ULL, b ) )||
       (! does_extended_decimal_round_to_given_binary( base_c, base_d, a,             b ) )||
       (! does_extended_decimal_round_to_given_binary( next_c, next_d, a + 0x0400ULL, b ) ))
        return  0;

    // 4. Using binary search, compute range of attraction: range of decimals
    //    around (base_c * 10^base_d) such that every number within it is mapped to 
    //    (a * 2^b) using convert_extended_decimal_to_binary_and_round().
    //    (prev_c * 10^base_d) and (next_c * 10^base_d) are known to be outside 
    //    this range of attraction, so lower bound is somewhere between prev_c and base_c
    //    and upper bound is somewhere between base_c and next_c.
    uint64_t  negative_extent = 0, negative_search_space = base_c - prev_c;
    uint64_t  positive_extent = 0, positive_search_space = next_c - base_c;
    for( uint64_t  bit = 1ULL << (63 - count_leading_zeros( negative_search_space )); bit != 0; bit >>= 1 )
    {
        if(( bit <= negative_search_space )&&
           ( does_extended_decimal_round_to_given_binary( base_c - negative_extent - bit,
                                                          base_d, a, b ) ))
        {
            negative_extent       += bit;
            negative_search_space -= bit;
        }
    }
    for( uint64_t  bit = 1ULL << (63 - count_leading_zeros( positive_search_space )); bit != 0; bit >>= 1 )
    {
        if(( bit <= positive_search_space )&&
           ( does_extended_decimal_round_to_given_binary( base_c + positive_extent + bit,
                                                          base_d, a, b ) ))
        {
            positive_extent       += bit;
            positive_search_space -= bit;
        }
    }

    // 5. Compute new decimal mantissa within range of attraction: digit after digit, most significant first
    uint64_t  new_mantissa = 0;
    for( uint64_t  current_scale = POW10_18; current_scale != 0; current_scale /= 10ULL )
    {
        uint64_t  next_digit = ((base_c + positive_extent) / current_scale) % 10ULL;
        new_mantissa += (current_scale * next_digit);
        if(( base_c - negative_extent <= new_mantissa )&&( new_mantissa <= base_c + positive_extent ))
            break;
    }

    // 6. Perform final normalization and offload results
    if( new_mantissa < POW10_18 )
    {
        new_mantissa *= 10ULL;
        --base_d;
    }
    (*c) = new_mantissa;
    (*d) = base_d;
    return  1;
}

//=====================================================================================================

/**
 *
 *  Unpack floating-point double precision binary value according to IEEE 754
 *
 */
static void  unpack_ieee754_double(
    const double*  input,
    int*           out_is_nan,
    int*           out_sign,
    uint64_t*      out_binary_mantissa,
    int32_t*       out_binary_exponent,
    int*           out_is_infinity
)
{
    // 1. Unpack bits
    uint64_t  input_bits     = *( (const uint64_t*)input );
    uint64_t  input_sign     = (input_bits >> 63);
    uint64_t  input_exponent = (input_bits >> 52) & 0x7FFULL;
    uint64_t  input_mantissa = (input_bits & ((1ULL << 52) - 1ULL));

    // 2. Handle special case: NaN
    if(( input_exponent == 0x7FFULL )&&( input_mantissa != 0 ))
    {
        *out_is_nan          = 1;
        *out_sign            = 0;
        *out_is_infinity     = 0;
        *out_binary_exponent = 0;
        *out_binary_mantissa = 0;
        return;
    }
    *out_is_nan = 0;
  
    // 3. Handle special case: +INF/-INF
    *out_sign = (input_sign != 0);
    if( input_exponent == 0x7FFULL )
    {
        *out_is_infinity     = 1;
        *out_binary_exponent = 0;
        *out_binary_mantissa = 0;
        return;
    }
    *out_is_infinity = 0;

    // 4. Handle special case: +0/-0
    if(( input_exponent == 0 )&&( input_mantissa == 0 ))
    {
        *out_binary_exponent = 0;
        *out_binary_mantissa = 0;
        return;
    }

    // 5. Handle denormalized numbers
    if( input_exponent == 0 )
    {
        *out_binary_exponent = -1022;
        *out_binary_mantissa = (input_mantissa << 11);   // most significant 53rd bit of mantissa is always 0
        return;
    }

    // 6. Handle normalized numbers
    *out_binary_exponent = ((int32_t)input_exponent) - 1023;
    *out_binary_mantissa = (1ULL << 63) | (input_mantissa << 11);   // 53rd bit of mantissa is always 1
}

/**
 *
 *  Pack floating-point double precision binary value according to IEEE 754
 *
 *  @returns  0  overflow / underflow condition (when strtod(3) would have set errno = ERANGE).
 *            1  exited normally, neither overflow nor underflow
 *
 */
static int  pack_ieee754_double(
    int       input_is_nan,
    int       input_sign,
    uint64_t  input_binary_mantissa,
    int32_t   input_binary_exponent,
    int       input_is_infinity,
    double*   output
)
{
    // 1. Initialize values to pack
    uint64_t  output_sign     = 0;
    uint64_t  output_exponent = 0;
    uint64_t  output_mantissa = 0;

    // 2. Handle special case: NaN
    int  had_overflow_or_underflow_in_exponent = 0;
    if( input_is_nan )
    {
        output_sign     = 1;              // Quiet NaN
        output_exponent = 0x7FF;
        output_mantissa = (1ULL << 51);   // mantissa MSB set
    }
    else
    {
        // 3. Handle special case: +INF/-INF
        output_sign = (input_sign ? 1 : 0);
        if( input_is_infinity )
        {
            output_exponent = 0x7FF;
            output_mantissa = 0;
        }
        // 4. Handle special case: +0/-0
        else if( input_binary_mantissa == 0 )
        {
            output_exponent = 0;
            output_mantissa = 0;
        }
        else
        {
            unsigned int  lz = count_leading_zeros( input_binary_mantissa );
            input_binary_mantissa <<= lz;
            input_binary_exponent  -= lz;

            if( input_binary_exponent > 1023 )
            {
                // 5. Handle unintentional infinity (due to exponent overflow)
                output_exponent = 0x7FF;
                output_mantissa = 0;
                had_overflow_or_underflow_in_exponent = 1;
            }
            else if( input_binary_exponent >= -1022 )
            {
                // 6. Handle normalized numbers
                output_exponent = ((uint64_t)( input_binary_exponent + 1023 ));
                output_mantissa = (input_binary_mantissa >> 11) & ((1ULL << 52) - 1ULL);
            }
            else
            {
                // 7. Handle denormalized numbers
                //    and unintentional zero (due to exponent underflow)
                input_binary_mantissa >>= 11;
                while(( input_binary_mantissa != 0 )&&( input_binary_exponent < -1022 ))
                {
                    input_binary_mantissa >>= 1;
                    ++input_binary_exponent;
                }
                output_exponent = 0;
                output_mantissa = input_binary_mantissa;
                had_overflow_or_underflow_in_exponent = (input_binary_mantissa == 0);
            }
        }
    }

    // 8. Pack bits up
    uint64_t  output_bits = (output_sign << 63) |
                            ((output_exponent & 0x7FFULL) << 52) |
                            (output_mantissa & ((1ULL << 52) - 1ULL));
    *( (uint64_t*)output ) = output_bits;
    return(! had_overflow_or_underflow_in_exponent );
}

/**
 *
 *  Decompress small integer in range 0..9999 to four-digit BCD representation
 *
 */
static inline void  bcd_decompress_small(
    uint32_t  compressed_bcd,
    uint8_t*  decompressed_bcd
)
{
    uint32_t  high_pair = compressed_bcd / 100;
    uint32_t  low_pair  = compressed_bcd % 100;

    decompressed_bcd[0] = ((uint8_t)( high_pair / 10 ));
    decompressed_bcd[1] = ((uint8_t)( high_pair % 10 ));
    decompressed_bcd[2] = ((uint8_t)( low_pair  / 10 ));
    decompressed_bcd[3] = ((uint8_t)( low_pair  % 10 ));
}

/**
 *
 *  Decompress full range unsigned 64-bit integer to twenty-digit BCD representation
 *
 *  This implementation was written by Douglas W. Jones, it was taken from
 *  http://homepage.cs.uiowa.edu/~jones/bcd/decimal.html#sixtyfour
 *
 */
static void  bcd_decompress(
    uint64_t  compressed_bcd,
    uint8_t*  decompressed_bcd
)
{
    uint32_t  d0 = compressed_bcd         & 0xFFFF;
    uint32_t  d1 = (compressed_bcd >> 16) & 0xFFFF;
    uint32_t  d2 = (compressed_bcd >> 32) & 0xFFFF;
    uint32_t  d3 = (compressed_bcd >> 48) & 0xFFFF;

              d0 = 656 * d3 + 7296 * d2 + 5536 * d1 + d0;
    uint32_t  q  = d0 / 10000;
              d0 = d0 % 10000;

              d1 = q + 7671 * d3 + 9496 * d2 + 6 * d1;
              q  = d1 / 10000;
              d1 = d1 % 10000;

              d2 = q + 4749 * d3 + 42 * d2;
              q  = d2 / 10000;
              d2 = d2 % 10000;

              d3 = q + 281 * d3;
              q  = d3 / 10000;
              d3 = d3 % 10000;

    bcd_decompress_small( q,  decompressed_bcd      );
    bcd_decompress_small( d3, decompressed_bcd + 4  );
    bcd_decompress_small( d2, decompressed_bcd + 8  );
    bcd_decompress_small( d1, decompressed_bcd + 12 );
    bcd_decompress_small( d0, decompressed_bcd + 16 );
}

/**
 *
 *  Compress four-digit BCD representation to small integer in range 0..9999
 *
 */
static inline uint32_t  bcd_compress_small( const uint8_t*  decompressed_bcd )
{
    uint32_t  high_pair = 10 * decompressed_bcd[0] + decompressed_bcd[1];
    uint32_t  low_pair  = 10 * decompressed_bcd[2] + decompressed_bcd[3];
    return  100 * high_pair + low_pair;
}

/**
 *
 *  Compress twenty-digit BCD representation to full range unsigned 64-bit integer
 *
 */
static uint64_t  bcd_compress( const uint8_t*  decompressed_bcd )
{
    uint64_t  d2 =         bcd_compress_small( decompressed_bcd      );
    uint64_t  d1 = 10000 * bcd_compress_small( decompressed_bcd + 4  )
                         + bcd_compress_small( decompressed_bcd + 8  );
    uint64_t  d0 = 10000 * bcd_compress_small( decompressed_bcd + 12 )
                         + bcd_compress_small( decompressed_bcd + 16 );
    return  ((d2 * (10000ULL * 10000ULL) + d1) * (10000ULL * 10000ULL)) + d0;
}

/**
 *
 *  Round twenty-digit BCD representation to given number of significant digits
 *
 *  Most significant digit must be always equal to zero.
 *  Therefore, number of significant digits can be in range from 1 to 19.
 *
 *  @returns  Adjusted number of significant decimal digits
 *
 */
static int  bcd_round( int  new_ndigits, uint8_t*  decimal_mantissa, int32_t*  exponent )
{
    // 1. Bounds check and adjustment
    if( new_ndigits < 1 )
        new_ndigits = 1;
    else if( new_ndigits > 19 )
        new_ndigits = 19;

    if( new_ndigits < 19 )
    {
        for( ;; )
        {
            // 2. Compute round-up flag
            int  round_up = ( decimal_mantissa[1 + new_ndigits] >= 5 );

            // 3. Zero out the tail
            for( int  i = 1 + new_ndigits; i < 20; ++i )
                decimal_mantissa[i] = 0;

            // 4. Make round-up if necessary
            if(! round_up )
                break;
            for( int  i = new_ndigits; i >= 0; --i )
            {
                uint8_t  new_value = decimal_mantissa[i] + 1;
                if( new_value < 10 )
                {
                    decimal_mantissa[i] = new_value;
                    break;
                }
                decimal_mantissa[i] = 0;
            }

            // 5. Handle overflow
            if( decimal_mantissa[0] == 0 )
                break;     // no overflow
            else
            {
                memmove( decimal_mantissa + 1, decimal_mantissa, 19 );
                decimal_mantissa[0] = 0;
                ++( *exponent );
                // if there was an overflow, then make one more iteration
            }
        }
    }

    // 6. Return adjusted number of significant decimal digits to the caller
    return  new_ndigits;
}

//=====================================================================================================

/**
 *
 *  Helper formatting function: Print given number of whitespaces to output buffer
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Overflow in the output buffer.
 *
 */
static int  format_pad( char**  outbuf, int*  outbuf_size, int  n )
{
    if( *outbuf_size < n )
        return  0;
    else
    {
        *outbuf_size -= n;
        char*  p = *outbuf;
        while( n-- > 0 )
            *p++ = ' ';
        *outbuf = p;
        return  1;
    }
}

/**
 *
 *  Helper formatting function: Print one character to output buffer
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Overflow in the output buffer.
 *
 */
static int  format_onechar( char**  outbuf, int*  outbuf_size, int  c )
{
    if( *outbuf_size <= 0 )
        return  0;
    else
    {
        *((*outbuf)++) = ((char)c);
        --(*outbuf_size);
        return  1;
    }
}

/**
 *
 *  Helper formatting function: Print given string to output buffer
 *
 *  @returns  1  Exited normally, no errors.
 *            0  Overflow in the output buffer.
 *
 */
static int  format_copystr( char**  outbuf, int*  outbuf_size, const char*  str, int  str_size )
{
    if( *outbuf_size < str_size )
        return  0;
    else
    {
        *outbuf_size -= str_size;
        char*  p = *outbuf;
        while( str_size-- > 0 )
            *p++ = *str++;
        *outbuf = p;
        return  1;
    }
}

/**
 *
 *  Helper formatting function: Print exponent like sprintf( p, "e%+02d", e )
 *
 *  There must be at least 16 bytes in the output buffer.
 *
 */
static void  format_exponent( char*  buffer, int32_t  exponent, int  is_uppercase )
{
    char  tmp_buffer[12];

    *buffer++ = (is_uppercase ? 'E' : 'e');
    if( exponent < 0 )
    {
        *buffer++ = '-';
        exponent = -exponent;
    }
    else
        *buffer++ = '+';

    int  i = 0;
    while(( exponent > 0 )&&( i < 12 ))
    {
        tmp_buffer[i++] = ((char)( (exponent % 10) + '0' ));
        exponent /= 10;
    }
    while( i < 2 )
        tmp_buffer[i++] = '0';
    while( i > 0 )
        *buffer++ = tmp_buffer[--i];
    *buffer = 0;
}

/**
 *
 *  Print IEEE 754 floating-point double precision value to string
 *
 *  @param  outbuf            Address of variable with a pointer to output buffer filled by the function.
 *                            On entry, this variable is initialized by caller.
 *                            On exit, this variable points to the end of printed string.
 *                           
 *  @param  outbuf_size       Size of output buffer filled by the function.
 *                            On entry, this variable is initialized by caller to maximum allowed size.
 *                            On exit, this variable contains size of unused portion of the output buffer.
 *                           
 *  @param  value             Input value (IEEE 754 floating-point double precision).
 *                           
 *  @param  format_char       Format char. Either 'e', or 'f', or 'g'. Refer to printf(3) manual for details.
 *                           
 *  @param  format_flags      Any combination of the above (DCONVSTR_FLAG_*).
 *                           
 *  @param  format_width      Format width. Used only if DCONVSTR_FLAG_HAVE_WIDTH bit is set in flags.
 *                            Refer to printf(3) manual for details.
 *
 *  @param  format_precision  Format precision. Set it to DCONVSTR_DEFAULT_PRECISION if unsure.
 *                            Refer to printf(3) manual for details.
 *
 *  @returns  1  if value was successfully converted to string.
 *            0  if there is not enough room in buffer or internal error happened during conversion.
 *
 */
int  dconvstr_print(
    char**        outbuf,
    int*          outbuf_size,
    double        value,
    int           format_char,
    unsigned int  format_flags,
    int           format_width,
    int           format_precision
)
{
    // 1. Unpack double precision value
    int       is_nan      = 0;
    int       is_negative = 0;
    int       is_infinity = 0;
    uint64_t  mantissa    = 0;
    int32_t   exponent    = 0;
    unpack_ieee754_double( &value, &is_nan, &is_negative, &mantissa, &exponent, &is_infinity );

    // 2. Handle special cases
    if( is_nan )
    {
        if( format_flags & DCONVSTR_FLAG_UPPERCASE )
            return  format_copystr( outbuf, outbuf_size, "NAN", 3 );
        else
            return  format_copystr( outbuf, outbuf_size, "nan", 3 );
    }
    if(( is_infinity )&&( !is_negative ))
    {
        if( format_flags & DCONVSTR_FLAG_UPPERCASE )
            return  format_copystr( outbuf, outbuf_size, "INF", 3 );
        else
            return  format_copystr( outbuf, outbuf_size, "inf", 3 );
    }
    if(( is_infinity )&&( is_negative ))
    {
        if( format_flags & DCONVSTR_FLAG_UPPERCASE )
            return  format_copystr( outbuf, outbuf_size, "-INF", 4 );
        else
            return  format_copystr( outbuf, outbuf_size, "-inf", 4 );
    }

    // 3. Get exact decimal representation.
    //    Decimal point is located on the right side of decimal mantissa
    uint8_t  decimal_mantissa[20];
    if( mantissa == 0 )
    {
        memset( decimal_mantissa, 0, sizeof(decimal_mantissa) );
        exponent = -18;
    }
    else
    {
        if(! convert_binary_to_extended_decimal( mantissa, exponent, &mantissa, &exponent ) )
            return  0;    // internal error during conversion
        bcd_decompress( mantissa, decimal_mantissa );
        if(( decimal_mantissa[0] != 0 )||( decimal_mantissa[1] == 0 ))
            return  0;    // invariant does not hold : mantissa >= 10^19 || mantissa < 10^18
    }

    // 4. Compute the following fields:
    //    z1      - number of zeros inserted before the digits
    //    z2      - number of zeros inserted after the digits
    //    point   - number of digits printed before decimal point
    //    ndigits - number of digits to print from decimal_mantissa[1..19].
    //    suffix  - formatted exponent like "e-5"
    //    (Code from this section was adopted from http://golang.org/src/lib9/fmt/fltfmt.c)
    int   point   = 1;
    int   z1      = 0;
    int   z2      = 0;
    int   ndigits = 19;      // initially we have 19 digits (most significant zero digit is ignored)
    char  suffix[16];
    int   suffix_width = 0;

    int  original_format_char = format_char;
    if( format_char == 'g' )
    {
        // get rid of excess precision
        if( format_precision == 0 )
            format_precision = 1;
        if( format_precision < ndigits )
        {
            exponent += (ndigits - format_precision);  // retain invariant "point after mantissa"
            ndigits = bcd_round( format_precision, decimal_mantissa, &exponent );
        }
    
        // choose format: e or f
        int  e = exponent + (ndigits - 1);  // now point is after mantissa, move to the left (after 1st digit)
        if(( e >= -4 )&&( e < format_precision ))    // so printf(3) rules say
        {
            format_char = 'f';
        }
        else
        {
            format_char = 'e';
            --format_precision;             // one digit before the point, rest after
        }
    }

    if( format_char == 'e' )
    {
        exponent += (ndigits - 1);    // now point is after mantissa, move to the left (after 1st digit)

        // compute trailing zero padding or truncate digits
        if( 1 + format_precision >= ndigits )
            z2 = 1 + format_precision - ndigits;
        else
            ndigits = bcd_round( 1 + format_precision, decimal_mantissa, &exponent );

        format_exponent( suffix, exponent, format_flags & DCONVSTR_FLAG_UPPERCASE );
        suffix_width = ((int)( strlen( suffix ) ));
    }
    else if( format_char == 'f' )
    {
        // determine where digits go with respect to decimal point
        if( ndigits + exponent > 0 )
        {
            point = ndigits + exponent;
            z1    = 0;
        }
        else
        {
            point = 1;
            z1    = 1 + -(ndigits + exponent);
        }

        // %g specifies prec = number of significant digits
        // convert to number of digits after decimal point
        if( original_format_char == 'g' )
            format_precision += (z1 - point);

        // compute trailing zero padding or truncate digits
        if( point + format_precision >= z1 + ndigits )
            z2 = point + format_precision - (z1 + ndigits);
        else
        {
            int  new_ndigits = point + format_precision - z1;
            if( new_ndigits < 0 )
            {
                z1 += new_ndigits;
                ndigits = 0;
            }
            else if( new_ndigits == 0 )
            {
                if( decimal_mantissa[1] >= 5 )
                {
                    decimal_mantissa[1] = 1;
                    ndigits = 1;
                    if( z1 > 0 )
                        --z1;
                    else
                        ++point;
                }
            }
            else
            {
                int  new_exponent = exponent;
                ndigits = bcd_round( new_ndigits, decimal_mantissa, &new_exponent );
                for( ; new_exponent > exponent; --new_exponent )
                {
                    ++z2;
                    if( z1 > 0 )
                        --z1;
                    else
                        ++point;
                }
            }
        }
        suffix_width = 0;
    }
    else
        return  0;

    // 5. If %g is given without DCONVSTR_FLAG_SHARP, remove trailing zeros.
    //    Must do after truncation, so that e.g. print %.3g 1.001 produces 1, not 1.00.
    //    Sorry, but them's the rules.
    if(( original_format_char == 'g'      )&&
       ( !(format_flags & DCONVSTR_FLAG_SHARP) )&&
       ( z1 + ndigits + z2 >= point       ))
    {
        if( z1 + ndigits < point )
            z2 = point - (z1 + ndigits);
        else
        {
            z2 = 0;
            while(( z1 + ndigits > point )&&( decimal_mantissa[ndigits] == 0 ))
                --ndigits;
        }
    }

    // 6. Compute width of all digits and decimal point and suffix if any
    int  total_width = z1 + ndigits + z2;
    if( total_width > point )
        total_width += 1;
    else if( total_width == point )
    {
        if( format_flags & DCONVSTR_FLAG_SHARP )
            total_width += 1;
        else
            ++point;        // point is not printed at the end
    }
    total_width += suffix_width;

    // 7. Determine sign
    int  sign = 0;
    if( is_negative )
        sign = '-';
    else
    {
        if( format_flags & DCONVSTR_FLAG_PRINT_PLUS )
            sign = '+';
        if( format_flags & DCONVSTR_FLAG_SPACE_IF_PLUS )
            sign = ' ';
    }
    if( sign )
        ++total_width;

    // 8. Compute padding
    int  padding = 0;
    if(( format_flags & DCONVSTR_FLAG_HAVE_WIDTH )&&( format_width > total_width ))
        padding = format_width - total_width;
    if(( padding                                 )&&
       ( !(format_flags & DCONVSTR_FLAG_LEFT_JUSTIFY) )&&
       ( format_flags & DCONVSTR_FLAG_PAD_WITH_ZERO   ))
    {
        z1     += padding;
        point  += padding;
        padding = 0;
    }

    // 9. Collect everything together and dump to output buffer
    if(( padding                                      )&&
       ( !(format_flags & DCONVSTR_FLAG_LEFT_JUSTIFY) )&&
       ( !format_pad( outbuf, outbuf_size, padding )  ))
        return  0;
    if(( sign )&&(! format_onechar( outbuf, outbuf_size, sign ) ))
        return  0;
    const unsigned char*  digits = decimal_mantissa + 1;
    while(( z1 > 0 )||( ndigits > 0 )||( z2 > 0 ))
    {
        int  c = '0';
        if( z1 > 0 )
            z1--;
        else if( ndigits > 0 )
        {
            ndigits--;
            c = '0' + (*digits++);
        }
        else
            z2--;
        if(! format_onechar( outbuf, outbuf_size, c ) )
            return  0;
        if(( --point == 0 )&&(! format_onechar( outbuf, outbuf_size, '.' ) ))
            return  0;
    }
    if(( suffix_width )&&(! format_copystr( outbuf, outbuf_size, suffix, suffix_width ) ))
        return  0;
    if(( padding                                     )&&
       ( format_flags & DCONVSTR_FLAG_LEFT_JUSTIFY   )&&
       ( !format_pad( outbuf, outbuf_size, padding ) ))
        return  0;
    return  1;
}

/**
 *
 *  Convert string to IEEE 754 floating-point double precision value
 *
 *  @param  input          Input buffer, C-style string. Filled by caller.
 *
 *  @param  input_end      Address of pointer to end of scanned value in input buffer.
 *                         Filled by function if address is not NULL.
 *
 *  @param  output         Conversion result (IEEE 754 floating-point double precision).
 *                         Set to 0.0 if string in input buffer has syntax errors.
 *
 *  @param  output_erange  Address of overflow/underflow flag variable, filled by function.
 *                         0  if there is no overflow/underflow condition
 *                         1  if there is overflow/underflow condition: strtod(3) would set errno = ERANGE
 *
 *  @returns  1  if there were no internal errors
 *            0  if there was internal error during conversion.
 *
 *  In general, interface of this function is similar to strtod(3), except for returning overflow
 *  condition instead of setting errno. If you want just to convert C-style string to double with
 *  error checking, then set input_end != NULL and use ( ret_value != 0 )&&( **input_end == 0 )
 *  condition as an indication of successful conversion.
 *
 */
int  dconvstr_scan(
    const char*   input,
    const char**  input_end,
    double*       output,
    int*          output_erange
)
{
    // 1. Handle special cases
    if((( input[0] == 'n' )||( input[0] == 'N' ))&&
       (( input[1] == 'a' )||( input[1] == 'A' ))&&
       (( input[2] == 'n' )||( input[2] == 'N' )))
    {
        if( input_end )
            *input_end = input + 3;

        pack_ieee754_double(
            1,      // input_is_nan
            0,      // input_sign
            0,      // input_binary_mantissa
            0,      // input_binary_exponent
            0,      // input_is_infinity
            output
        );
        *output_erange = 0;
        return  1;
    }
    else if((( input[0] == 'i' )||( input[0] == 'I' ))&&
            (( input[1] == 'n' )||( input[1] == 'N' ))&&
            (( input[2] == 'f' )||( input[2] == 'F' )))
    {
        if( input_end )
            *input_end = input + 3;

        pack_ieee754_double(
            0,      // input_is_nan
            0,      // input_sign
            0,      // input_binary_mantissa
            0,      // input_binary_exponent
            1,      // input_is_infinity
            output
        );
        *output_erange = 0;
        return  1;
    }
    else if(( input[0] == '-' )&&
            (( input[1] == 'i' )||( input[1] == 'I' ))&&
            (( input[2] == 'n' )||( input[2] == 'N' ))&&
            (( input[3] == 'f' )||( input[3] == 'F' )))
    {
        if( input_end )
            *input_end = input + 4;

        pack_ieee754_double(
            0,      // input_is_nan
            1,      // input_sign
            0,      // input_binary_mantissa
            0,      // input_binary_exponent
            1,      // input_is_infinity
            output
        );
        *output_erange = 0;
        return  1;
    }

    // 2. Parse input string
    //    (Code from this section was adopted from http://golang.org/src/lib9/fmt/fltfmt.c)
    uint8_t  parsed_digits[20];
    int      n_parsed_digits        = 0;      // number of digits in parsed_digits[]
    int32_t  exponent               = 0;
    int32_t  exponent_offset        = 0;
    int      flag_negative_mantissa = 0;
    int      flag_negative_exponent = 0;
    int      flag_syntax_error      = 0;

    enum parser_state  state = S0;
        // S0: _          _S0   +S1   #S2   .S3
        // S1: _+         #S2   .S3
        // S2: _+#        #S2   .S4   eS5
        // S3: _+#.       #S4
        // S4: _+#.#      #S4   eS5
        // S5: _+#.#e     +S6   #S7
        // S6: _+#.#e+    #S7
        // S7: _+#.#e+#   #S7
    const char*  s = input;
    while(( !flag_syntax_error )&&( *s ))
    {
        char  ch = *s;
        switch( state )
        {
            // State 0: skip leading whitespaces, before mantissa sign and digits
            case S0:
                if(( ch == ' ' )||( ch == '\t' ))
                    ++s;  // remain in state S0
                else if( ch == '-' )
                {
                    ++s;
                    state = S1;
                    flag_negative_mantissa = 1;
                }
                else if( ch == '+' )
                {
                    ++s;
                    state = S1;
                }
                else if(( ch >= '0' )&&( ch <= '9' ))
                {
                    state = S2;
                }
                else if( ch == '.' )
                {
                    ++s;
                    state = S3;
                }
                else
                    flag_syntax_error = 1;
                break;

            // State 1: after mantissa sign, before mantissa digits
            case S1:
                if(( ch >= '0' )&&( ch <= '9' ))
                    state = S2;
                else if( ch == '.' )
                {
                    ++s;
                    state = S3;
                }
                else
                    flag_syntax_error = 1;
                break;

            // State 2: parsing mantissa digits before point
            case S2:
                if(( ch >= '0' )&&( ch <= '9' ))
                {
                    ++s;
                    if( n_parsed_digits < ((int)( sizeof(parsed_digits) )) )
                    {
                        parsed_digits[n_parsed_digits] = ch - '0';
                        if(( ch != '0' )||( n_parsed_digits != 0 ))
                            ++n_parsed_digits;
                    }
                    else
                        ++exponent_offset;
                }
                else if( ch == '.' )
                {
                    ++s;
                    state = S3;
                }
                else if(( ch == 'e' )||( ch == 'E' ))
                {
                    ++s;
                    state = S5;
                }
                else
                    flag_syntax_error = 1;
                break;

            // State 3: parsing first mantissa digit just after the point
            case S3:
                if(( ch >= '0' )&&( ch <= '9' ))
                    state = S4;
                else
                    flag_syntax_error = 1;
                break;

            // State 4: parsing mantissa digits after the point
            case S4:
                if(( ch >= '0' )&&( ch <= '9' ))
                {
                    ++s;
                    if( n_parsed_digits < ((int)( sizeof(parsed_digits) )) )
                    {
                        parsed_digits[n_parsed_digits] = ch - '0';
                        if(( ch != '0' )||( n_parsed_digits != 0 ))
                            ++n_parsed_digits;
                        --exponent_offset;
                    }
                }
                else if(( ch == 'e' )||( ch == 'E' ))
                {
                    ++s;
                    state = S5;
                }
                else
                    flag_syntax_error = 1;
                break;

            // State 5: parsing sign after the exponent
            case S5:
                if(( ch >= '0' )&&( ch <= '9' ))
                    state = S7;
                else if( ch == '+' )
                {
                    ++s;
                    state = S6;
                }
                else if( ch == '-' )
                {
                    ++s;
                    state = S6;
                    flag_negative_exponent = 1;
                }
                else
                    flag_syntax_error = 1;
                break;

            // State 6: parsing first digits after exponent sign
            case S6:
                if(( ch >= '0' )&&( ch <= '9' ))
                    state = S7;
                else
                    flag_syntax_error = 1;
                break;

            // State 7: parsing exponent digits
            case S7:
                if(( ch >= '0' )&&( ch <= '9' )) 
                {
                    ++s;
                    if( exponent < 350 )
                    {
                        // we aim to avoid overflow/underflow of the exponent 
                        // by using ( exponent >= 350 ) condition as overflow/underflow flag
                        exponent = (exponent * 10) + (ch - '0');
                    }
                }
                else
                    flag_syntax_error = 1;
                break;
        }
    }
    if((! flag_syntax_error )&&(( state == S0 )||( state == S1 )||( state == S3 )||
                                ( state == S5 )||( state == S6 )))
        flag_syntax_error = 1;
    if( input_end )
        *input_end = flag_syntax_error ? input : s;

    // 3. Zero out the tail of mantissa.
    //    Move decimal point to the right side of mantissa (adjust exponent offset).
    //    Get rid of last mantissa digit, set first one to zero, and compress BCD representation of mantissa.
    if( n_parsed_digits < ((int)( sizeof(parsed_digits) )) )
    {
        int  delta = sizeof(parsed_digits) - n_parsed_digits;
        memset( parsed_digits + n_parsed_digits, 0, delta );
        n_parsed_digits += delta;
        exponent_offset -= delta;
    }
    memmove( parsed_digits + 1, parsed_digits, sizeof(parsed_digits) - 1 ); 
    parsed_digits[0] = 0;
    ++exponent_offset;
    uint64_t  mantissa = bcd_compress( parsed_digits );

    // 4. Compute exponent
    if( mantissa == 0 )
        exponent = 0;
    else
        exponent = ( (exponent < 350) ? exponent_offset : 0 ) +
                   ( flag_negative_exponent ? -exponent : exponent );

    // 5. Check exponent for overflow and underflow
    if( exponent <= -350 )
    {
        pack_ieee754_double(
            0,                       // input_is_nan
            flag_negative_mantissa,  // input_sign
            0,                       // input_binary_mantissa
            0,                       // input_binary_exponent
            0,                       // input_is_infinity
            output
        );
        *output_erange = 1;      // strtod(3) would set errno = ERANGE
        return  1;
    }
    else if( exponent >= 350 )
    {
        pack_ieee754_double(
            0,                       // input_is_nan
            flag_negative_mantissa,  // input_sign
            0,                       // input_binary_mantissa
            0,                       // input_binary_exponent
            1,                       // input_is_infinity
            output
        );
        *output_erange = 1;      // strtod(3) would set errno = ERANGE
        return  1;
    }

    // 6. Convert to binary representation, pack bits up and exit
    if( mantissa != 0 )
    {
        if(! convert_extended_decimal_to_binary_and_round( mantissa, exponent, &mantissa, &exponent ) )
            return  0;           // internal error
    }
    *output_erange = (! pack_ieee754_double(
        0,                       // input_is_nan
        flag_negative_mantissa,  // input_sign
        mantissa,                // input_binary_mantissa
        exponent,                // input_binary_exponent
        0,                       // input_is_infinity
        output
    ) );
    return  1;
}