/* POTM ENTRY: primeval */ /* Your Name: Allan Wilks */ /* Your email: allan@research.att.com */ /* cc primeval.c -o primeval */ /* This is primeval, a program to solve the POTM problem due on 15 Jan 1995. In a nutshell, find the largest prime in a 5x5 grid of digits using the standard adjacency graph to construct a path of digits for the prime. */ /* Together the nbr1[] and nbr2[] arrays encode all neighbor information for the 5x5 grid. The grid positions are numbered this way: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 An integer (called a grid bit-vector) is used to represent a subset of the grid locations, with a 1 in bit position i if grid cell i is in the subset. (Bit position 0 is the low bit of the integer.) Given such an integer, b say, the integer representing the subset of neighbors of the cells represented by b is then given by nbr1[b & 0x1fff] | nbr2[b >> 13] In other words, nbr1[] encodes all neighbor sets of subsets of the first 13 cells and nbr2[] encodes all neighbor sets of subsets of the last 12 cells. */ #define ALL 0x1ffffff #define NBR(b) nbr1[(b) & 0x1fff] | nbr2[(b) >> 13] int nbr1[] = { 0,98,229,231,458,490,495,495,916,1014,1013,1015,990, 1022,1023,1023,776,874,1005,1007,970,1002,1007,1007,924, 1022,1021,1023,990,1022,1023,1023,3139,3171,3303,3303,3531, 3563,3567,3567,4055,4087,4087,4087,4063,4095,4095,4095, 3915,3947,4079,4079,4043,4075,4079,4079,4063,4095,4095, 4095,4063,4095,4095,4095,7335,7399,7399,7399,7663,7663, 7663,7663,8119,8183,8183,8183,8191,8191,8191,8191,8111, 8175,8175,8175,8175,8175,8175,8175,8127,8191,8191,8191, 8191,8191,8191,8191,7399,7399,7399,7399,7663,7663,7663, 7663,8183,8183,8183,8183,8191,8191,8191,8191,8175,8175, 8175,8175,8175,8175,8175,8175,8191,8191,8191,8191,8191, 8191,8191,8191,14670,14702,14831,14831,14798,14830,14831, 14831,15326,15358,15359,15359,15326,15358,15359,15359,15182, 15214,15343,15343,15310,15342,15343,15343,15326,15358,15359, 15359,15326,15358,15359,15359,15695,15727,15855,15855,15823, 15855,15855,15855,16351,16383,16383,16383,16351,16383,16383, 16383,16207,16239,16367,16367,16335,16367,16367,16367,16351, 16383,16383,16383,16351,16383,16383,16383,15855,15855,15855, 15855,15855,15855,15855,15855,16383,16383,16383,16383,16383, 16383,16383,16383,16367,16367,16367,16367,16367,16367,16367, 16367,16383,16383,16383,16383,16383,16383,16383,16383,15855, 15855,15855,15855,15855,15855,15855,15855,16383,16383,16383, 16383,16383,16383,16383,16383,16367,16367,16367,16367,16367, 16367,16367,16367,16383,16383,16383,16383,16383,16383,16383, 16383,29340,29438,29437,29439,29662,29694,29695,29695,29596, 29694,29693,29695,29662,29694,29695,29695,29596,29694,29693, 29695,29662,29694,29695,29695,29596,29694,29693,29695,29662, 29694,29695,29695,32479,32511,32511,32511,32735,32767,32767, 32767,32735,32767,32767,32767,32735,32767,32767,32767,32735, 32767,32767,32767,32735,32767,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32447,32511,32511,32511,32767, 32767,32767,32767,32703,32767,32767,32767,32767,32767,32767, 32767,32703,32767,32767,32767,32767,32767,32767,32767,32703, 32767,32767,32767,32767,32767,32767,32767,32511,32511,32511, 32511,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,31710, 31742,31743,31743,31710,31742,31743,31743,31710,31742,31743, 31743,31710,31742,31743,31743,31710,31742,31743,31743,31710, 31742,31743,31743,31710,31742,31743,31743,31710,31742,31743, 31743,32735,32767,32767,32767,32735,32767,32767,32767,32735, 32767,32767,32767,32735,32767,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32735,32767,32767,32767,32735, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,24856,24954,25085, 25087,25050,25082,25087,25087,25500,25598,25597,25599,25566, 25598,25599,25599,25368,25466,25597,25599,25562,25594,25599, 25599,25500,25598,25597,25599,25566,25598,25599,25599,27995, 28027,28159,28159,28123,28155,28159,28159,28639,28671,28671, 28671,28639,28671,28671,28671,28507,28539,28671,28671,28635, 28667,28671,28671,28639,28671,28671,28671,28639,28671,28671, 28671,32191,32255,32255,32255,32255,32255,32255,32255,32703, 32767,32767,32767,32767,32767,32767,32767,32703,32767,32767, 32767,32767,32767,32767,32767,32703,32767,32767,32767,32767, 32767,32767,32767,32255,32255,32255,32255,32255,32255,32255, 32255,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,31070,31102,31231,31231,31198, 31230,31231,31231,31710,31742,31743,31743,31710,31742,31743, 31743,31582,31614,31743,31743,31710,31742,31743,31743,31710, 31742,31743,31743,31710,31742,31743,31743,32095,32127,32255, 32255,32223,32255,32255,32255,32735,32767,32767,32767,32735, 32767,32767,32767,32607,32639,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32735,32767,32767,32767,32255, 32255,32255,32255,32255,32255,32255,32255,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32255,32255,32255,32255,32255,32255,32255,32255,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,29596,29694,29693,29695,29662,29694,29695, 29695,29596,29694,29693,29695,29662,29694,29695,29695,29596, 29694,29693,29695,29662,29694,29695,29695,29596,29694,29693, 29695,29662,29694,29695,29695,32735,32767,32767,32767,32735, 32767,32767,32767,32735,32767,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32735,32767,32767,32767,32735, 32767,32767,32767,32735,32767,32767,32767,32703,32767,32767, 32767,32767,32767,32767,32767,32703,32767,32767,32767,32767, 32767,32767,32767,32703,32767,32767,32767,32767,32767,32767, 32767,32703,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,31710,31742,31743,31743,31710,31742,31743,31743,31710, 31742,31743,31743,31710,31742,31743,31743,31710,31742,31743, 31743,31710,31742,31743,31743,31710,31742,31743,31743,31710, 31742,31743,31743,32735,32767,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32735,32767,32767,32767,32735, 32767,32767,32767,32735,32767,32767,32767,32735,32767,32767, 32767,32735,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,32767, 32767,32767,32767,32767,32767,32767,32767,32767,32767,100448, 100450,100581,100583,100842,100842,100847,100847,101364, 101366,101365,101367,101374,101374,101375,101375,101224, 101226,101357,101359,101354,101354,101359,101359,101372, 101374,101373,101375,101374,101374,101375,101375,101475, 101475,101607,101607,101867,101867,101871,101871,102391, 102391,102391,102391,102399,102399,102399,102399,102251, 102251,102383,102383,102379,102379,102383,102383,102399, 102399,102399,102399,102399,102399,102399,102399,105703, 105703,105703,105703,105967,105967,105967,105967,106487, 106487,106487,106487,106495,106495,106495,106495,106479, 106479,106479,106479,106479,106479,106479,106479,106495, 106495,106495,106495,106495,106495,106495,106495,105703, 105703,105703,105703,105967,105967,105967,105967,106487, 106487,106487,106487,106495,106495,106495,106495,106479, 106479,106479,106479,106479,106479,106479,106479,106495, 106495,106495,106495,106495,106495,106495,106495,113006, 113006,113135,113135,113134,113134,113135,113135,113662, 113662,113663,113663,113662,113662,113663,113663,113518, 113518,113647,113647,113646,113646,113647,113647,113662, 113662,113663,113663,113662,113662,113663,113663,114031, 114031,114159,114159,114159,114159,114159,114159,114687, 114687,114687,114687,114687,114687,114687,114687,114543, 114543,114671,114671,114671,114671,114671,114671,114687, 114687,114687,114687,114687,114687,114687,114687,114159, 114159,114159,114159,114159,114159,114159,114159,114687, 114687,114687,114687,114687,114687,114687,114687,114671, 114671,114671,114671,114671,114671,114671,114671,114687, 114687,114687,114687,114687,114687,114687,114687,114159, 114159,114159,114159,114159,114159,114159,114159,114687, 114687,114687,114687,114687,114687,114687,114687,114671, 114671,114671,114671,114671,114671,114671,114671,114687, 114687,114687,114687,114687,114687,114687,114687,129788, 129790,129789,129791,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,130815, 130815,130815,130815,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130815, 130815,130815,130815,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130815, 130815,130815,130815,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,125304, 125306,125437,125439,125434,125434,125439,125439,125948, 125950,125949,125951,125950,125950,125951,125951,125816, 125818,125949,125951,125946,125946,125951,125951,125948, 125950,125949,125951,125950,125950,125951,125951,126331, 126331,126463,126463,126459,126459,126463,126463,126975, 126975,126975,126975,126975,126975,126975,126975,126843, 126843,126975,126975,126971,126971,126975,126975,126975, 126975,126975,126975,126975,126975,126975,126975,130559, 130559,130559,130559,130559,130559,130559,130559,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130559, 130559,130559,130559,130559,130559,130559,130559,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,129406, 129406,129535,129535,129534,129534,129535,129535,130046, 130046,130047,130047,130046,130046,130047,130047,129918, 129918,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,130431, 130431,130559,130559,130559,130559,130559,130559,131071, 131071,131071,131071,131071,131071,131071,131071,130943, 130943,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130559, 130559,130559,130559,130559,130559,130559,130559,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130559, 130559,130559,130559,130559,130559,130559,130559,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130044, 130046,130045,130047,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,130044, 130046,130045,130047,130046,130046,130047,130047,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,130046, 130046,130047,130047,130046,130046,130047,130047,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,131071, 131071,131071,131071,131071,131071,131071,131071,234720, 234722,234725,234727,234986,234986,234991,234991,235508, 235510,235509,235511,235518,235518,235519,235519,235496, 235498,235501,235503,235498,235498,235503,235503,235516, 235518,235517,235519,235518,235518,235519,235519,236771, 236771,236775,236775,237035,237035,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237547, 237547,237551,237551,237547,237547,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,236775, 236775,236775,236775,237039,237039,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237551, 237551,237551,237551,237551,237551,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,236775, 236775,236775,236775,237039,237039,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237551, 237551,237551,237551,237551,237551,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,245230, 245230,245231,245231,245230,245230,245231,245231,245758, 245758,245759,245759,245758,245758,245759,245759,245742, 245742,245743,245743,245742,245742,245743,245743,245758, 245758,245759,245759,245758,245758,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,259836, 259838,259837,259839,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,259576, 259578,259581,259583,259578,259578,259583,259583,260092, 260094,260093,260095,260094,260094,260095,260095,260088, 260090,260093,260095,260090,260090,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,261627, 261627,261631,261631,261627,261627,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262139, 262139,262143,262143,262139,262139,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261630, 261630,261631,261631,261630,261630,261631,261631,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,260092, 260094,260093,260095,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,260092, 260094,260093,260095,260094,260094,260095,260095,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,236768, 236770,236773,236775,237034,237034,237039,237039,237556, 237558,237557,237559,237566,237566,237567,237567,237544, 237546,237549,237551,237546,237546,237551,237551,237564, 237566,237565,237567,237566,237566,237567,237567,236771, 236771,236775,236775,237035,237035,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237547, 237547,237551,237551,237547,237547,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,236775, 236775,236775,236775,237039,237039,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237551, 237551,237551,237551,237551,237551,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,236775, 236775,236775,236775,237039,237039,237039,237039,237559, 237559,237559,237559,237567,237567,237567,237567,237551, 237551,237551,237551,237551,237551,237551,237551,237567, 237567,237567,237567,237567,237567,237567,237567,245230, 245230,245231,245231,245230,245230,245231,245231,245758, 245758,245759,245759,245758,245758,245759,245759,245742, 245742,245743,245743,245742,245742,245743,245743,245758, 245758,245759,245759,245758,245758,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,245231, 245231,245231,245231,245231,245231,245231,245231,245759, 245759,245759,245759,245759,245759,245759,245759,245743, 245743,245743,245743,245743,245743,245743,245743,245759, 245759,245759,245759,245759,245759,245759,245759,261884, 261886,261885,261887,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261887, 261887,261887,261887,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261624, 261626,261629,261631,261626,261626,261631,261631,262140, 262142,262141,262143,262142,262142,262143,262143,262136, 262138,262141,262143,262138,262138,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,261627, 261627,261631,261631,261627,261627,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262139, 262139,262143,262143,262139,262139,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261630, 261630,261631,261631,261630,261630,261631,261631,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,261631, 261631,261631,261631,261631,261631,261631,261631,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262140, 262142,262141,262143,262142,262142,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262142, 262142,262143,262143,262142,262142,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,262143, 262143,262143,262143,262143,262143,262143,262143,469440, 469474,469477,469479,469450,469482,469487,469487,469972, 470006,470005,470007,469982,470014,470015,470015,469960, 469994,469997,469999,469962,469994,469999,469999,469980, 470014,470013,470015,469982,470014,470015,470015,470467, 470499,470503,470503,470475,470507,470511,470511,470999, 471031,471031,471031,471007,471039,471039,471039,470987, 471019,471023,471023,470987,471019,471023,471023,471007, 471039,471039,471039,471007,471039,471039,471039,474599, 474599,474599,474599,474607,474607,474607,474607,475127, 475127,475127,475127,475135,475135,475135,475135,475119, 475119,475119,475119,475119,475119,475119,475119,475135, 475135,475135,475135,475135,475135,475135,475135,474599, 474599,474599,474599,474607,474607,474607,474607,475127, 475127,475127,475127,475135,475135,475135,475135,475119, 475119,475119,475119,475119,475119,475119,475119,475135, 475135,475135,475135,475135,475135,475135,475135,473550, 473582,473583,473583,473550,473582,473583,473583,474078, 474110,474111,474111,474078,474110,474111,474111,474062, 474094,474095,474095,474062,474094,474095,474095,474078, 474110,474111,474111,474078,474110,474111,474111,474575, 474607,474607,474607,474575,474607,474607,474607,475103, 475135,475135,475135,475103,475135,475135,475135,475087, 475119,475119,475119,475087,475119,475119,475119,475103, 475135,475135,475135,475103,475135,475135,475135,474607, 474607,474607,474607,474607,474607,474607,474607,475135, 475135,475135,475135,475135,475135,475135,475135,475119, 475119,475119,475119,475119,475119,475119,475119,475135, 475135,475135,475135,475135,475135,475135,475135,474607, 474607,474607,474607,474607,474607,474607,474607,475135, 475135,475135,475135,475135,475135,475135,475135,475119, 475119,475119,475119,475119,475119,475119,475119,475135, 475135,475135,475135,475135,475135,475135,475135,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,485848, 485882,485885,485887,485850,485882,485887,485887,486364, 486398,486397,486399,486366,486398,486399,486399,486360, 486394,486397,486399,486362,486394,486399,486399,486364, 486398,486397,486399,486366,486398,486399,486399,486875, 486907,486911,486911,486875,486907,486911,486911,487391, 487423,487423,487423,487391,487423,487423,487423,487387, 487419,487423,487423,487387,487419,487423,487423,487391, 487423,487423,487423,487391,487423,487423,487423,491007, 491007,491007,491007,491007,491007,491007,491007,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491007, 491007,491007,491007,491007,491007,491007,491007,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,489950, 489982,489983,489983,489950,489982,489983,489983,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490975, 491007,491007,491007,490975,491007,491007,491007,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491007, 491007,491007,491007,491007,491007,491007,491007,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491007, 491007,491007,491007,491007,491007,491007,491007,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,490460, 490494,490493,490495,490462,490494,490495,490495,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,490462, 490494,490495,490495,490462,490494,490495,490495,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491487, 491519,491519,491519,491487,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,491519, 491519,491519,491519,491519,491519,491519,491519,502240, 502242,502245,502247,502250,502250,502255,502255,502772, 502774,502773,502775,502782,502782,502783,502783,502760, 502762,502765,502767,502762,502762,502767,502767,502780, 502782,502781,502783,502782,502782,502783,502783,503267, 503267,503271,503271,503275,503275,503279,503279,503799, 503799,503799,503799,503807,503807,503807,503807,503787, 503787,503791,503791,503787,503787,503791,503791,503807, 503807,503807,503807,503807,503807,503807,503807,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,506350, 506350,506351,506351,506350,506350,506351,506351,506878, 506878,506879,506879,506878,506878,506879,506879,506862, 506862,506863,506863,506862,506862,506863,506863,506878, 506878,506879,506879,506878,506878,506879,506879,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,518648, 518650,518653,518655,518650,518650,518655,518655,519164, 519166,519165,519167,519166,519166,519167,519167,519160, 519162,519165,519167,519162,519162,519167,519167,519164, 519166,519165,519167,519166,519166,519167,519167,519675, 519675,519679,519679,519675,519675,519679,519679,520191, 520191,520191,520191,520191,520191,520191,520191,520187, 520187,520191,520191,520187,520187,520191,520191,520191, 520191,520191,520191,520191,520191,520191,520191,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,522750, 522750,522751,522751,522750,522750,522751,522751,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,523260, 523262,523261,523263,523262,523262,523263,523263,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,523262, 523262,523263,523263,523262,523262,523263,523263,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,507360, 507362,507365,507367,507370,507370,507375,507375,507892, 507894,507893,507895,507902,507902,507903,507903,507880, 507882,507885,507887,507882,507882,507887,507887,507900, 507902,507901,507903,507902,507902,507903,507903,507363, 507363,507367,507367,507371,507371,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507883, 507883,507887,507887,507883,507883,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507374, 507374,507375,507375,507374,507374,507375,507375,507902, 507902,507903,507903,507902,507902,507903,507903,507886, 507886,507887,507887,507886,507886,507887,507887,507902, 507902,507903,507903,507902,507902,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523768, 523770,523773,523775,523770,523770,523775,523775,524284, 524286,524285,524287,524286,524286,524287,524287,524280, 524282,524285,524287,524282,524282,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,523771, 523771,523775,523775,523771,523771,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524283, 524283,524287,524287,524283,524283,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523774, 523774,523775,523775,523774,523774,523775,523775,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,507360, 507362,507365,507367,507370,507370,507375,507375,507892, 507894,507893,507895,507902,507902,507903,507903,507880, 507882,507885,507887,507882,507882,507887,507887,507900, 507902,507901,507903,507902,507902,507903,507903,507363, 507363,507367,507367,507371,507371,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507883, 507883,507887,507887,507883,507883,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507367, 507367,507367,507367,507375,507375,507375,507375,507895, 507895,507895,507895,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507374, 507374,507375,507375,507374,507374,507375,507375,507902, 507902,507903,507903,507902,507902,507903,507903,507886, 507886,507887,507887,507886,507886,507887,507887,507902, 507902,507903,507903,507902,507902,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,507375, 507375,507375,507375,507375,507375,507375,507375,507903, 507903,507903,507903,507903,507903,507903,507903,507887, 507887,507887,507887,507887,507887,507887,507887,507903, 507903,507903,507903,507903,507903,507903,507903,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523768, 523770,523773,523775,523770,523770,523775,523775,524284, 524286,524285,524287,524286,524286,524287,524287,524280, 524282,524285,524287,524282,524282,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,523771, 523771,523775,523775,523771,523771,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524283, 524283,524287,524287,524283,524283,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523774, 523774,523775,523775,523774,523774,523775,523775,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,523775, 523775,523775,523775,523775,523775,523775,523775,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524284, 524286,524285,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524286, 524286,524287,524287,524286,524286,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287,524287, 524287,524287,524287,524287,524287,524287,524287}; int nbr2[] = { 0,938880,795392,947072,3214336,4153216,4009728,4161408, 7511040,8314752,8306432,8322944,7576576,8380288,8371968, 8388480,15022080,15694720,15547136,15694720,16071680,16744320, 16596736,16744320,16235520,16777088,16760576,16777088,16235520, 16777088,16760576,16777088,30044160,30307200,30307072,30307200, 33258496,33521536,33521408,33521536,33225728,33488768,33488640, 33488768,33291264,33554304,33554176,33554304,32471040,32471936, 32471808,32471936,33520640,33521536,33521408,33521536,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 25452544,26112896,25977600,26112896,28666880,29327232,29191936, 29327232,32963584,33488768,33488640,33488768,33029120,33554304, 33554176,33554304,31815680,32471936,32340736,32471936,32865280, 33521536,33390336,33521536,33029120,33554304,33554176,33554304, 33029120,33554304,33554176,33554304,30306304,30307200,30307072, 30307200,33520640,33521536,33521408,33521536,33487872,33488768, 33488640,33488768,33553408,33554304,33554176,33554304,32471040, 32471936,32471808,32471936,33520640,33521536,33521408,33521536, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,2195456,3134336,2990848,3142528,3247104,4185984, 4042496,4194176,7576576,8380288,8371968,8388480,7576576, 8380288,8371968,8388480,15054848,15727488,15579904,15727488, 16104448,16777088,16629504,16777088,16235520,16777088,16760576, 16777088,16235520,16777088,16760576,16777088,32239616,32502656, 32502528,32502656,33291264,33554304,33554176,33554304,33291264, 33554304,33554176,33554304,33291264,33554304,33554176,33554304, 32503808,32504704,32504576,32504704,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,27648000,28308352,28173056,28308352,28699648, 29360000,29224704,29360000,33029120,33554304,33554176,33554304, 33029120,33554304,33554176,33554304,31848448,32504704,32373504, 32504704,32898048,33554304,33423104,33554304,33029120,33554304, 33554176,33554304,33029120,33554304,33554176,33554304,32501760, 32502656,32502528,32502656,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32503808,32504704,32504576,32504704,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,5472256,6280064,6267648,6288256, 7572480,8380288,8367872,8388480,7576576,8380288,8371968, 8388480,7576576,8380288,8371968,8388480,16234496,16776064, 16759552,16776064,16235520,16777088,16760576,16777088,16235520, 16777088,16760576,16777088,16235520,16777088,16760576,16777088, 31191040,31454080,31453952,31454080,33291264,33554304,33554176, 33554304,33291264,33554304,33554176,33554304,33291264,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,30924800,31454080,31449856, 31454080,33025024,33554304,33550080,33554304,33029120,33554304, 33554176,33554304,33029120,33554304,33554176,33554304,33028096, 33553280,33553152,33553280,33029120,33554304,33554176,33554304, 33029120,33554304,33554176,33554304,33029120,33554304,33554176, 33554304,31453184,31454080,31453952,31454080,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,7569408,8377216, 8364800,8385408,7572480,8380288,8367872,8388480,7576576, 8380288,8371968,8388480,7576576,8380288,8371968,8388480, 16234496,16776064,16759552,16776064,16235520,16777088,16760576, 16777088,16235520,16777088,16760576,16777088,16235520,16777088, 16760576,16777088,33288192,33551232,33551104,33551232,33291264, 33554304,33554176,33554304,33291264,33554304,33554176,33554304, 33291264,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33021952, 33551232,33547008,33551232,33025024,33554304,33550080,33554304, 33029120,33554304,33554176,33554304,33029120,33554304,33554176, 33554304,33028096,33553280,33553152,33553280,33029120,33554304, 33554176,33554304,33029120,33554304,33554176,33554304,33029120, 33554304,33554176,33554304,33550336,33551232,33551104,33551232, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 10944512,11490176,11477760,11498368,11996160,12541824,12529408, 12550016,16227328,16768896,16760576,16777088,16227328,16768896, 16760576,16777088,15153152,15694720,15678208,15694720,16202752, 16744320,16727808,16744320,16235520,16777088,16760576,16777088, 16235520,16777088,16760576,16777088,32468992,32469888,32469760, 32469888,33520640,33521536,33521408,33521536,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32471040, 32471936,32471808,32471936,33520640,33521536,33521408,33521536, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,27746304,28275584,28271360,28275584,28797952,29327232, 29323008,29327232,33029120,33554304,33554176,33554304,33029120, 33554304,33554176,33554304,31946752,32471936,32471808,32471936, 32996352,33521536,33521408,33521536,33029120,33554304,33554176, 33554304,33029120,33554304,33554176,33554304,32468992,32469888, 32469760,32469888,33520640,33521536,33521408,33521536,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32471040,32471936,32471808,32471936,33520640,33521536,33521408, 33521536,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,10977280,11522944,11510528,11531136,12028928, 12574592,12562176,12582784,16227328,16768896,16760576,16777088, 16227328,16768896,16760576,16777088,15185920,15727488,15710976, 15727488,16235520,16777088,16760576,16777088,16235520,16777088, 16760576,16777088,16235520,16777088,16760576,16777088,32501760, 32502656,32502528,32502656,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32503808,32504704,32504576,32504704,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,27779072,28308352,28304128,28308352, 28830720,29360000,29355776,29360000,33029120,33554304,33554176, 33554304,33029120,33554304,33554176,33554304,31979520,32504704, 32504576,32504704,33029120,33554304,33554176,33554304,33029120, 33554304,33554176,33554304,33029120,33554304,33554176,33554304, 32501760,32502656,32502528,32502656,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32503808,32504704,32504576,32504704,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,16220160,16765824,16753408, 16774016,16223232,16768896,16756480,16777088,16227328,16768896, 16760576,16777088,16227328,16768896,16760576,16777088,16234496, 16776064,16759552,16776064,16235520,16777088,16760576,16777088, 16235520,16777088,16760576,16777088,16235520,16777088,16760576, 16777088,33550336,33551232,33551104,33551232,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33021952,33551232, 33547008,33551232,33025024,33554304,33550080,33554304,33029120, 33554304,33554176,33554304,33029120,33554304,33554176,33554304, 33028096,33553280,33553152,33553280,33029120,33554304,33554176, 33554304,33029120,33554304,33554176,33554304,33029120,33554304, 33554176,33554304,33550336,33551232,33551104,33551232,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,16220160, 16765824,16753408,16774016,16223232,16768896,16756480,16777088, 16227328,16768896,16760576,16777088,16227328,16768896,16760576, 16777088,16234496,16776064,16759552,16776064,16235520,16777088, 16760576,16777088,16235520,16777088,16760576,16777088,16235520, 16777088,16760576,16777088,33550336,33551232,33551104,33551232, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33021952,33551232,33547008,33551232,33025024,33554304,33550080, 33554304,33029120,33554304,33554176,33554304,33029120,33554304, 33554176,33554304,33028096,33553280,33553152,33553280,33029120, 33554304,33554176,33554304,33029120,33554304,33554176,33554304, 33029120,33554304,33554176,33554304,33550336,33551232,33551104, 33551232,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,21889024,21910400,21897984,21918592,25103360,25124736, 25112320,25132928,25074688,25091968,25083648,25100160,25140224, 25157504,25149184,25165696,32454656,32471936,32455424,32471936, 33504256,33521536,33505024,33521536,33537024,33554304,33537792, 33554304,33537024,33554304,33537792,33554304,30306304,30307200, 30307072,30307200,33520640,33521536,33521408,33521536,33487872, 33488768,33488640,33488768,33553408,33554304,33554176,33554304, 32471040,32471936,32471808,32471936,33520640,33521536,33521408, 33521536,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,30302208,30307200,30302976,30307200,33516544, 33521536,33517312,33521536,33487872,33488768,33488640,33488768, 33553408,33554304,33554176,33554304,32471040,32471936,32471808, 32471936,33520640,33521536,33521408,33521536,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,30306304, 30307200,30307072,30307200,33520640,33521536,33521408,33521536, 33487872,33488768,33488640,33488768,33553408,33554304,33554176, 33554304,32471040,32471936,32471808,32471936,33520640,33521536, 33521408,33521536,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,24084480,24105856,24093440,24114048, 25136128,25157504,25145088,25165696,25140224,25157504,25149184, 25165696,25140224,25157504,25149184,25165696,32487424,32504704, 32488192,32504704,33537024,33554304,33537792,33554304,33537024, 33554304,33537792,33554304,33537024,33554304,33537792,33554304, 32501760,32502656,32502528,32502656,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32503808,32504704,32504576,32504704,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32497664,32502656,32498432, 32502656,33549312,33554304,33550080,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32503808, 32504704,32504576,32504704,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32501760,32502656,32502528,32502656,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32503808,32504704,32504576,32504704, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,23035904,23057280, 23044864,23065472,25136128,25157504,25145088,25165696,25140224, 25157504,25149184,25165696,25140224,25157504,25149184,25165696, 33536000,33553280,33536768,33553280,33537024,33554304,33537792, 33554304,33537024,33554304,33537792,33554304,33537024,33554304, 33537792,33554304,31453184,31454080,31453952,31454080,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,31449088, 31454080,31449856,31454080,33549312,33554304,33550080,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,31453184,31454080,31453952,31454080, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 25133056,25154432,25142016,25162624,25136128,25157504,25145088, 25165696,25140224,25157504,25149184,25165696,25140224,25157504, 25149184,25165696,33536000,33553280,33536768,33553280,33537024, 33554304,33537792,33554304,33537024,33554304,33537792,33554304, 33537024,33554304,33537792,33554304,33550336,33551232,33551104, 33551232,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33546240,33551232,33547008,33551232,33549312,33554304, 33550080,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33550336,33551232, 33551104,33551232,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33552384,33553280,33553152,33553280,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32440320,32461696,32449280,32469888,33491968, 33513344,33500928,33521536,33528832,33546112,33537792,33554304, 33528832,33546112,33537792,33554304,32454656,32471936,32455424, 32471936,33504256,33521536,33505024,33521536,33537024,33554304, 33537792,33554304,33537024,33554304,33537792,33554304,32468992, 32469888,32469760,32469888,33520640,33521536,33521408,33521536, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32471040,32471936,32471808,32471936,33520640,33521536, 33521408,33521536,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32464896,32469888,32465664,32469888, 33516544,33521536,33517312,33521536,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32471040,32471936, 32471808,32471936,33520640,33521536,33521408,33521536,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32468992,32469888,32469760,32469888,33520640,33521536,33521408, 33521536,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32471040,32471936,32471808,32471936,33520640, 33521536,33521408,33521536,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32473088,32494464,32482048, 32502656,33524736,33546112,33533696,33554304,33528832,33546112, 33537792,33554304,33528832,33546112,33537792,33554304,32487424, 32504704,32488192,32504704,33537024,33554304,33537792,33554304, 33537024,33554304,33537792,33554304,33537024,33554304,33537792, 33554304,32501760,32502656,32502528,32502656,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32503808,32504704,32504576,32504704, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32497664,32502656, 32498432,32502656,33549312,33554304,33550080,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32503808,32504704,32504576,32504704,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32501760,32502656,32502528,32502656,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32503808,32504704,32504576, 32504704,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33521664, 33543040,33530624,33551232,33524736,33546112,33533696,33554304, 33528832,33546112,33537792,33554304,33528832,33546112,33537792, 33554304,33536000,33553280,33536768,33553280,33537024,33554304, 33537792,33554304,33537024,33554304,33537792,33554304,33537024, 33554304,33537792,33554304,33550336,33551232,33551104,33551232, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33546240,33551232,33547008,33551232,33549312,33554304,33550080, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33550336,33551232,33551104, 33551232,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33521664,33543040,33530624,33551232,33524736,33546112, 33533696,33554304,33528832,33546112,33537792,33554304,33528832, 33546112,33537792,33554304,33536000,33553280,33536768,33553280, 33537024,33554304,33537792,33554304,33537024,33554304,33537792, 33554304,33537024,33554304,33537792,33554304,33550336,33551232, 33551104,33551232,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33552384,33553280,33553152,33553280,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33546240,33551232,33547008,33551232,33549312, 33554304,33550080,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33550336, 33551232,33551104,33551232,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,9175040,9327488,9184000,9335680, 12389376,12541824,12398336,12550016,16686080,16703360,16695040, 16711552,16751616,16768896,16760576,16777088,15546368,15694720, 15547136,15694720,16595968,16744320,16596736,16744320,16759808, 16777088,16760576,16777088,16759808,16777088,16760576,16777088, 30306304,30307200,30307072,30307200,33520640,33521536,33521408, 33521536,33487872,33488768,33488640,33488768,33553408,33554304, 33554176,33554304,32471040,32471936,32471808,32471936,33520640, 33521536,33521408,33521536,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,25976832,26112896,25977600, 26112896,29191168,29327232,29191936,29327232,33487872,33488768, 33488640,33488768,33553408,33554304,33554176,33554304,32339968, 32471936,32340736,32471936,33389568,33521536,33390336,33521536, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,30306304,30307200,30307072,30307200,33520640,33521536, 33521408,33521536,33487872,33488768,33488640,33488768,33553408, 33554304,33554176,33554304,32471040,32471936,32471808,32471936, 33520640,33521536,33521408,33521536,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,11370496,11522944, 11379456,11531136,12422144,12574592,12431104,12582784,16751616, 16768896,16760576,16777088,16751616,16768896,16760576,16777088, 15579136,15727488,15579904,15727488,16628736,16777088,16629504, 16777088,16759808,16777088,16760576,16777088,16759808,16777088, 16760576,16777088,32501760,32502656,32502528,32502656,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32503808,32504704,32504576, 32504704,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,28172288, 28308352,28173056,28308352,29223936,29360000,29224704,29360000, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32372736,32504704,32373504,32504704,33422336,33554304, 33423104,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32501760,32502656,32502528,32502656, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32503808,32504704, 32504576,32504704,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 14647296,14668672,14656256,14676864,16747520,16768896,16756480, 16777088,16751616,16768896,16760576,16777088,16751616,16768896, 16760576,16777088,16758784,16776064,16759552,16776064,16759808, 16777088,16760576,16777088,16759808,16777088,16760576,16777088, 16759808,16777088,16760576,16777088,31453184,31454080,31453952, 31454080,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,31449088,31454080,31449856,31454080,33549312,33554304, 33550080,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,31453184,31454080, 31453952,31454080,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33552384,33553280,33553152,33553280,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,16744448,16765824,16753408,16774016,16747520, 16768896,16756480,16777088,16751616,16768896,16760576,16777088, 16751616,16768896,16760576,16777088,16758784,16776064,16759552, 16776064,16759808,16777088,16760576,16777088,16759808,16777088, 16760576,16777088,16759808,16777088,16760576,16777088,33550336, 33551232,33551104,33551232,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33546240,33551232,33547008,33551232, 33549312,33554304,33550080,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33550336,33551232,33551104,33551232,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,11468800,11490176,11477760, 11498368,12520448,12541824,12529408,12550016,16751616,16768896, 16760576,16777088,16751616,16768896,16760576,16777088,15677440, 15694720,15678208,15694720,16727040,16744320,16727808,16744320, 16759808,16777088,16760576,16777088,16759808,16777088,16760576, 16777088,32468992,32469888,32469760,32469888,33520640,33521536, 33521408,33521536,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32471040,32471936,32471808,32471936, 33520640,33521536,33521408,33521536,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,28270592,28275584, 28271360,28275584,29322240,29327232,29323008,29327232,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32471040,32471936,32471808,32471936,33520640,33521536,33521408, 33521536,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32468992,32469888,32469760,32469888,33520640, 33521536,33521408,33521536,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32471040,32471936,32471808, 32471936,33520640,33521536,33521408,33521536,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,11501568, 11522944,11510528,11531136,12553216,12574592,12562176,12582784, 16751616,16768896,16760576,16777088,16751616,16768896,16760576, 16777088,15710208,15727488,15710976,15727488,16759808,16777088, 16760576,16777088,16759808,16777088,16760576,16777088,16759808, 16777088,16760576,16777088,32501760,32502656,32502528,32502656, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32503808,32504704, 32504576,32504704,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 28303360,28308352,28304128,28308352,29355008,29360000,29355776, 29360000,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32503808,32504704,32504576,32504704,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32501760,32502656,32502528, 32502656,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32503808, 32504704,32504576,32504704,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,16744448,16765824,16753408,16774016,16747520,16768896, 16756480,16777088,16751616,16768896,16760576,16777088,16751616, 16768896,16760576,16777088,16758784,16776064,16759552,16776064, 16759808,16777088,16760576,16777088,16759808,16777088,16760576, 16777088,16759808,16777088,16760576,16777088,33550336,33551232, 33551104,33551232,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33552384,33553280,33553152,33553280,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33546240,33551232,33547008,33551232,33549312, 33554304,33550080,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33550336, 33551232,33551104,33551232,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,16744448,16765824,16753408,16774016, 16747520,16768896,16756480,16777088,16751616,16768896,16760576, 16777088,16751616,16768896,16760576,16777088,16758784,16776064, 16759552,16776064,16759808,16777088,16760576,16777088,16759808, 16777088,16760576,16777088,16759808,16777088,16760576,16777088, 33550336,33551232,33551104,33551232,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33546240,33551232,33547008, 33551232,33549312,33554304,33550080,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33550336,33551232,33551104,33551232,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,30277632,30299008, 30286592,30307200,33491968,33513344,33500928,33521536,33463296, 33480576,33472256,33488768,33528832,33546112,33537792,33554304, 32454656,32471936,32455424,32471936,33504256,33521536,33505024, 33521536,33537024,33554304,33537792,33554304,33537024,33554304, 33537792,33554304,30306304,30307200,30307072,30307200,33520640, 33521536,33521408,33521536,33487872,33488768,33488640,33488768, 33553408,33554304,33554176,33554304,32471040,32471936,32471808, 32471936,33520640,33521536,33521408,33521536,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,30302208, 30307200,30302976,30307200,33516544,33521536,33517312,33521536, 33487872,33488768,33488640,33488768,33553408,33554304,33554176, 33554304,32471040,32471936,32471808,32471936,33520640,33521536, 33521408,33521536,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,30306304,30307200,30307072,30307200, 33520640,33521536,33521408,33521536,33487872,33488768,33488640, 33488768,33553408,33554304,33554176,33554304,32471040,32471936, 32471808,32471936,33520640,33521536,33521408,33521536,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32473088,32494464,32482048,32502656,33524736,33546112,33533696, 33554304,33528832,33546112,33537792,33554304,33528832,33546112, 33537792,33554304,32487424,32504704,32488192,32504704,33537024, 33554304,33537792,33554304,33537024,33554304,33537792,33554304, 33537024,33554304,33537792,33554304,32501760,32502656,32502528, 32502656,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32503808, 32504704,32504576,32504704,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32497664,32502656,32498432,32502656,33549312,33554304, 33550080,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,32503808,32504704,32504576,32504704, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32501760,32502656, 32502528,32502656,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32503808,32504704,32504576,32504704,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,31424512,31445888,31433472,31454080,33524736, 33546112,33533696,33554304,33528832,33546112,33537792,33554304, 33528832,33546112,33537792,33554304,33536000,33553280,33536768, 33553280,33537024,33554304,33537792,33554304,33537024,33554304, 33537792,33554304,33537024,33554304,33537792,33554304,31453184, 31454080,31453952,31454080,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,31449088,31454080,31449856,31454080, 33549312,33554304,33550080,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 31453184,31454080,31453952,31454080,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33521664,33543040,33530624, 33551232,33524736,33546112,33533696,33554304,33528832,33546112, 33537792,33554304,33528832,33546112,33537792,33554304,33536000, 33553280,33536768,33553280,33537024,33554304,33537792,33554304, 33537024,33554304,33537792,33554304,33537024,33554304,33537792, 33554304,33550336,33551232,33551104,33551232,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33546240,33551232, 33547008,33551232,33549312,33554304,33550080,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33552384,33553280,33553152,33553280,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33550336,33551232,33551104,33551232,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32440320, 32461696,32449280,32469888,33491968,33513344,33500928,33521536, 33528832,33546112,33537792,33554304,33528832,33546112,33537792, 33554304,32454656,32471936,32455424,32471936,33504256,33521536, 33505024,33521536,33537024,33554304,33537792,33554304,33537024, 33554304,33537792,33554304,32468992,32469888,32469760,32469888, 33520640,33521536,33521408,33521536,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,32471040,32471936, 32471808,32471936,33520640,33521536,33521408,33521536,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32464896,32469888,32465664,32469888,33516544,33521536,33517312, 33521536,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32471040,32471936,32471808,32471936,33520640, 33521536,33521408,33521536,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32468992,32469888,32469760, 32469888,33520640,33521536,33521408,33521536,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32471040, 32471936,32471808,32471936,33520640,33521536,33521408,33521536, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32473088,32494464,32482048,32502656,33524736,33546112, 33533696,33554304,33528832,33546112,33537792,33554304,33528832, 33546112,33537792,33554304,32487424,32504704,32488192,32504704, 33537024,33554304,33537792,33554304,33537024,33554304,33537792, 33554304,33537024,33554304,33537792,33554304,32501760,32502656, 32502528,32502656,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 32503808,32504704,32504576,32504704,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,32497664,32502656,32498432,32502656,33549312, 33554304,33550080,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,32503808,32504704,32504576, 32504704,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,32501760, 32502656,32502528,32502656,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,32503808,32504704,32504576,32504704,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33521664,33543040,33530624,33551232, 33524736,33546112,33533696,33554304,33528832,33546112,33537792, 33554304,33528832,33546112,33537792,33554304,33536000,33553280, 33536768,33553280,33537024,33554304,33537792,33554304,33537024, 33554304,33537792,33554304,33537024,33554304,33537792,33554304, 33550336,33551232,33551104,33551232,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33552384,33553280,33553152,33553280,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33546240,33551232,33547008, 33551232,33549312,33554304,33550080,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33552384, 33553280,33553152,33553280,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33550336,33551232,33551104,33551232,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33552384,33553280,33553152,33553280, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33521664,33543040, 33530624,33551232,33524736,33546112,33533696,33554304,33528832, 33546112,33537792,33554304,33528832,33546112,33537792,33554304, 33536000,33553280,33536768,33553280,33537024,33554304,33537792, 33554304,33537024,33554304,33537792,33554304,33537024,33554304, 33537792,33554304,33550336,33551232,33551104,33551232,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304, 33553408,33554304,33554176,33554304,33552384,33553280,33553152, 33553280,33553408,33554304,33554176,33554304,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33546240, 33551232,33547008,33551232,33549312,33554304,33550080,33554304, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33552384,33553280,33553152,33553280,33553408,33554304, 33554176,33554304,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33550336,33551232,33551104,33551232, 33553408,33554304,33554176,33554304,33553408,33554304,33554176, 33554304,33553408,33554304,33554176,33554304,33552384,33553280, 33553152,33553280,33553408,33554304,33554176,33554304,33553408, 33554304,33554176,33554304,33553408,33554304,33554176,33554304}; /* Some digit bit-vectors. Each digit bit-vector represents a set of digits and has a 1 in position i if and only if i is in the set (again, bit 0 is the low bit). Three digits sets play an important role in "hard" grids, and each has a complement: set complement --- ---------- MOD31 (1, 4 or 7) OFF1 EVEN5 (even digits and 5) OFF2 MULT3 (multiple of 3) OFF3 A MOD31 grid (all digits are 1, 4 or 7) has no 3-digit, 6-digit or 9-digit primes (since then 3 divides the sum of the digits), an EVEN5 grid has largest prime equal to 2 or 5 and a MULT3 grid has largest prime equal to 3. One thing that can make a grid hard is if it is almost in one of three classes, i.e., if the number of OFF1 digits, say, is small but positive. */ #define D1 0x002 /* {1} */ #define EVEN 0x155 /* {02468} */ #define EVEN5 0x175 /* {024568} */ #define MULT3 0x249 /* {0369} */ #define MULT7 0x081 /* {07} */ #define MOD31 0x092 /* {147} */ #define OFF1 0x36d /* ~{147} = {0235689} */ #define OFF2 0x28a /* ~{024568} = {1379} */ #define OFF3 0x1b6 /* ~{0369} = {124578} */ /* print the prime and exit */ #define DONE(p) {printf("%d\n", p); exit(0);} /* grid[i] is a grid bit-vector giving the locations of digit i dig[i] is the i'th digit of the number being constructed; if k+1 is the number of digits in the number then dig is filled in the order dig[k], dig[k-1], ... nbr[i] is a grid bit-vector giving the relevant occurrences of dig[i]; all numbers in the grid with leading digits dig[k], ..., dig[i] are constructed in parallel and nbr[i] tells where the last of these digits occur; it may not (likely won't be) all occurrences of dig[i] in the grid (which would be grid[dig[i]]) sum[i] keeps a cumulative total of the number under construction: sum[i] = 10^k*dig[k] + 10^(k-1)*dig[k-1] + ... + 10^i*dig[i] */ int grid[10], dig[9], nbr[9], sum[9]; /* Each distx[i] is a grid bit-vector; bit j is 1 if and only if the distance from grid position j to the closest OFFx digit is at most i. So, for example, bit j of distx[0] is 1 if and only if the digit at grid position j is an OFFx digit. These bit-vectors are used to avoid wandering around in grids where it is important to reach a rare OFFx digit. */ int dist1[9] = {0,0,0,0,0,ALL,ALL,ALL,ALL}; int dist2[9] = {0,0,0,0,0,ALL,ALL,ALL,ALL}; int dist3[9] = {0,0,0,0,0,ALL,ALL,ALL,ALL}; /* The div3, div7 and div11 vectors are used to make digit-sum tests. This saves a little time because the computation of the integer to test for primality from its component digits can be avoided if the digit-sum test indicates a composite number. The entries in these vectors are 0 or 1; divx[i] is 1 if and only if i is a legitimate digit-sum for divisibility by x. The test for x=3 is whether the sum of the digits is divisible by 3. The test for x=7 is whether d0-d3+d6+2*(d2-d5+d8)+3*(d1-d4+d7) is divisible by 7 (with d0 being the 1's digit, d1 the 10's digit and so on). The test for x=11 is whether d0-d1+d2-d3+...+d8 is divisible by 11. Note that for x=7 and x=11 the digit-sums can be negative so div7 and div11 are set up so as to subscriptable by negative numbers. The index range for each divx is determined by the possible values of the corresponding digit sum. Note that it would be nice to also initialize the arrays here, but that would be indirectly building prime numbers into the code, which is against the rules. */ int div3[82], Div7[163], *div7 = Div7+54, Div11[82], *div11 = Div11+36; /* We need a small table (P) of TABSIZE primes, which we compute using a fairly simple seive (S). We will also need the approximate double precision inverses (Pi) of the primes in the table. */ #define TABSIZE 40 /* total number of primes needed */ #define BOOTSIZE 7 /* number of primes to bootstrap */ #define SEIVESIZE 170 /* size of seive */ int P[2*TABSIZE] = {2,3,5,7,11}, S[2*SEIVESIZE]; double Pi[2*TABSIZE]; /************************************************************************/ /* */ /* MAIN */ /* */ /************************************************************************/ main(ac, av) int ac; char **av; { int i, n, k, bits, n1, n2, n3, min12, min32; char buf[60]; /* Read the grid -- gutsy! */ read(open(av[1], 0), buf, 50); /* Record the locations of each digit, as well as a digit bit-vector of all the digits that appear. */ for(i = 0; i < 10; i++) grid[i] = 0; bits = 0; for(i = 0; i < 25; i++) { n = buf[2*i] - '0'; grid[n] |= 1 << i; bits |= 1 << n; } /* Take care of some easy cases; all even digits, etc. */ if((bits|EVEN) == EVEN) DONE(2); if((bits|MULT3) == MULT3) DONE(3); if((bits|EVEN5) == EVEN5) DONE(5); if((bits|MULT7) == MULT7) DONE(7); if(bits == D1) DONE(11); /* Now compute the distx grid bit-vectors. distx[0] is just the locations of the OFFx digits. Then distx[1] records the neighbors of the distx[0] digits, distx[2] records the neighbors of the distx[1] digits and so on. */ dist1[0] = ~(grid[1] | grid[4] | grid[7]) & ALL; for(i = 1; i < 5; i++) dist1[i] = NBR(dist1[i-1]); dist2[0] = grid[1] | grid[3] | grid[7] | grid[9]; for(i = 1; i < 5; i++) dist2[i] = NBR(dist2[i-1]); dist3[0] = ~(grid[0] | grid[3] | grid[6] | grid[9]) & ALL; for(i = 1; i < 5; i++) dist3[i] = NBR(dist3[i-1]); /* Compute min12, the smallest distance from an OFF1 digit to an OFF2 digit and min32, the smallest distance from an OFF3 to an OFF2 digit. */ for(min12 = 0; min12 < 5; min12++) if(dist1[min12] & dist2[0]) break; for(min32 = 0; min32 < 5; min32++) if(dist3[min32] & dist2[0]) break; /* Compute n1, n2 and n3, the numbers of OFF1, OFF2 and OFF3 digits. */ for(n1 = 0, n = dist1[0]; n; n >>= 1) if(n&1) n1++; for(n2 = 0, n = dist2[0]; n; n >>= 1) if(n&1) n2++; for(n3 = 0, n = dist3[0]; n; n >>= 1) if(n&1) n3++; /* Fill up the table of small primes. */ primetab(); /* Fill the digit-sum vectors; divx[i] is 1 when the corresponding digit-sum function indicates divisibility by x. */ for(i = 0; i < 82; i += 3) div3[i] = 1; for(i = -49; i < 108; i += 7) div7[i] = 1; for(i = -33; i < 45; i += 11) div11[i] = 1; /* Overall strategy: 1) start with 9-digit numbers unless there are no OFF1s (all digits are 1, 4 or 7), in which case start with k-digit numbers; 2) take special care when the number of OFF1s is small and the number of digits (k+1) is a multiple of 3; we will have to reach an OFF1 and then reach an OFF2 to finish; 3) take special care when the number of OFF3s is small; we will have to reach an OFF3 and then reach an OFF2 to finish; 4) otherwise, just an exhaustive search. The definition of "small" in cases 2) and 3) is "less than 6"; this is experimentally OK. */ for(k = n1?8:7; k >= 1; k--) if(n1 < 6 && k%3 == 2) onelength(k, OFF1, min12, dist1); else if(n3 < 6) onelength(k, OFF3, min32, dist3); else onelength(k, 0, 0, 0); /* Because of the structure of the code in onelength(), where the last digit of the number is treated specially, length-1 numbers are not handled properly. Hence the previous for-loop only checks down to 2-digit numbers. But 1-digit numbers are easy to check since we only have to check for the presence of the number (digit). */ if(grid[7]) DONE(7); if(grid[5]) DONE(5); if(grid[3]) DONE(3); if(grid[2]) DONE(2); /* Fred promises that there is a prime in the grid so we should never get here. */ DONE(0); } /************************************************************************/ /* */ /* ONELENGTH */ /* */ /************************************************************************/ /* The search routine. Length-(k+1) numbers are enumerated from largest to smallest and tested until a prime is found. Pos keeps track of the digit position within the number; pos=0 corresponds to the low order digit. The search is essentially breadth-first; all numbers with the same values for dig[k],...,dig[pos] are examined simultaneously. If the off argument is non-zero then special care is taken to avoid a lot of fruitless testing. It is a grid bit-vector representing the positions of either OFF1 digits or OFF3 digits; onelength() knows that it must include one of these in the numbers it creates. It uses the dist argument to keep track of how far it still has to go to reach one of the off digits. Once it does so, it uses the min argument to keep track of how far it still has to go to reach an OFF2 digit (with which all primes must end). */ onelength(k, off, min, dist) int k, off, min, *dist; { int i, m, n, pos, D, L, S, N, M; int d3, d4, d5, d6, d17, d28, d45, d167; int *vec, mark, bound; /* Set unused high-order digits to zero. */ for(i = k+1; i <= 8; i++) dig[i] = 0; /* Start pos at the high-order digit. The values of the digits seen so far are kept in dig[k], ..., dig[pos], and the value of dig[pos] is kept redundantly in D. D is only one of the possible values for the digit at position pos; the complete set of possibilities is the set of neighbors of the previous digit, dig[pos+1]. This set of neighbors is kept as a grid bit-vector in nbr[pos]. As a special case, since the leading digit can't be 0, nbr[k] indicates the set of non-zero grid positions. The value of nbr[pos] is stored redundantly in N. The number itself is accumulated in n, and the successive partial sums in the sum[] vector. This is more efficient than constructing it when ready to test for primality. */ pos = k; D = 10; N = nbr[k] = ALL & ~grid[0]; n = 0; /* In the special cases, we keep track of how well we are doing in finding an off digit and then finding an OFF2 digit. The mark variable keeps track of where the first off digit is in the number so far. Until that happens, vec is the dist vector of grid bit-vectors, used to monitor how close we are to an off digit. When one is seen, vec switches to point to the dist2 vector of grid bit-vectors, to monitor how close we are to the final OFF2 digit. The bound variable is an upper bound on the distance to either the needed off digit or the needed OFF2 digit; its initial value reflects the fact that we must reach the first off digit in k-min steps, since min is the minimum distance from an off digit to an OFF2 digit. */ if(off) { mark = -1; vec = dist; bound = k - min; } /* The loop that checks for numbers; the hope is that it will rarely complete to the bottom where the prime test is. */ while(1) { /* Look at the next lowest value of the current digit. Once it goes negative, we have run out of values for this digit and we must back up to the next higher digit in the number. */ if(--D < 0) { /* When we advance beyond the beginning of the number, we have examined all numbers of length k+1. */ if(++pos > k) break; else { /* Restore the values of n, D and N corresponding to the new (previous) digit position. */ n = sum[pos]; D = dig[pos]; N = nbr[pos]; /* In the special cases, relax the bound by 1. */ if(off) { bound++; /* If we just left the marked position, unset the mark, reset the vec, and recall that the bound now becomes tighter again by the amount we have to go once we reach the mark. */ if(mark == pos-1) { mark = -1; vec = dist; bound -= min; } } /* Now the current value of D is one we have tested so we go back to the top of the loop in order to decrement D. */ continue; } } /* The value assigned to S in the following expression is a grid bit-vector of all the occurrences of the digit D among the current set of neighbors. If there are none then we can go on to the next digit. */ if(!(S = N&grid[D])) continue; /* Now that we have a legitimate new digit, we need to treat the special cases, updating the values of mark, vec and bound. */ if(off) { /* If the new digit is an off digit and we haven't yet seen an off digit (mark < 0) then set mark to the current position, set vec to reflect the new distance criterion (distance to an OFF2) and relax the bound to allow for the minimum distance to an OFF2. */ if((1< 1) { dig[pos--] = D; /* A slightly faster way of multiplying by 10. */ n = sum[pos] = (n<<1) + (n<<3) + D; D = 10; /* Set nbr[pos] to the set of legitimate places we can go from here. */ N = nbr[pos] = NBR(S); /* In the special cases, the upper bound to getting to an off digit or an OFF2 digit gets tighter by 1. */ if(off) bound--; continue; } /* At this point, D is the 10's digit, and S is a grid bit-vector giving its legitimate locations. Set M to be the set of places we can look for the last digit and then set L to each possible value of the last digit, and test for primality. L can't be 5 or even. */ M = NBR(S); d6 = -1; m = 0; for(L = 9; L > 0; L -= 2) { /* Make sure there is at least on L in one of the M spots. */ if(L == 5 || !(M&grid[L])) continue; /* Here we compute some partial digit-sums. By careful arrangement, we can minimize the number of additions we have to do, and we only have to do the ones in this if() block once (d6 is used to detect if they have been done already; it's possible that the block never needs to be executed). The formulae are given in an earlier comment. */ if(d6 < 0) { d6 = dig[6]; d17 = D + dig[7]; d28 = dig[2] + dig[8]; d3 = dig[3]; d4 = dig[4]; d5 = dig[5]; d45 = d4 + d5; d167 = d6 + d17; } /* Do each of the digit-sum tests, ignoring this value of L if the test indicates that the number is divisible by 3, 7 or 11. */ if(div3[L+d167+d28+d45+d3]) continue; if(div7[L+d167 + ((d28+d17)<<1) - (d3+d4+(d45<<1))]) continue; if(div11[L+d6+d28+d4-(d17+d3+d5)]) continue; /* Complete the computation of the number by including the last two digits. All but the last addition needs only to be done once, so m keeps track of this. */ if(!m) { m = (n<<1) + (n<<3) + D; m = (m<<1) + (m<<3); } /* The prime test! */ if(isprime(m+L)) DONE(m+L); } } } /************************************************************************/ /* */ /* PRIMETAB */ /* */ /************************************************************************/ /* Initialize the prime table. First a small table of BOOTSIZE primes is computed by brute force (assumption: it is sufficient to test for divisibility of smaller primes up to only 5, i.e., the largest prime computed is less than 49, i.e., less than or equal to 47, i.e., BOOTSIZE is at most 15). Second, multiples of these primes, other than multiples of 2 and 3, are seived out. This means flagging these multiples of prime p: p, 5p, 7p, 12p, ... Third, seive elements that haven't been flagged and that don't correspond to multiples of 2 or 3 must be prime. Fourth, precompute the reciprocals (almost) of the primes in the table. Note that there is a subtle point here where the while loop begins: the value of q should be equal to -1 (mod 6). */ primetab() { int n = 5, p, q = 11, i, e, f; do { q++; if(q%2 && q%3 && q%5) P[n++] = q; } while(n < BOOTSIZE); for(i = 2; i < BOOTSIZE; i++) { p = P[i]; e = p << 1; f = e << 1; p = -p; while(p < SEIVESIZE) { S[p+=e] = 1; S[p+=f] = 1; } } while(q < SEIVESIZE) { if(S[q+=2] == 0) P[n++] = q; if(S[q+=4] == 0) P[n++] = q; } for(i = 0; i < TABSIZE; i++) Pi[i] = 1.00000000000001 / P[i]; } /************************************************************************/ /* */ /* ISPRIME */ /* */ /************************************************************************/ /* The test is in three stages. STAGE 1: Stage 1 tests directly for divisibilty by small primes. The first five primes have already been eliminated by digit tests, and so are not included in stage 1. The test used for divisibility is a floating point computation. Rather than doing integer divide for quotient and remainder, a single floating multiply is done. To test for divisibility of n by the small prime p, n is multiplied by a number that is slightly larger than the reciprocal of p. One can show that if this multiplication is performed with double precision IEEE arithmetic (as on the Sun), then n%p is 0 if and only if a certain collection of 12 (relatively low-order) bits of the product is identically zero. We test for 40 small primes -- this seems to give the right tradeoff between STAGE 1 and the remainder of the testing. Note that the test for divisibility by small primes will incorrectly flag the input as composite if it IS one of the small primes. However, one can show that no prime larger than 10 and smaller than 200 will ever be given to this routine. For example, if the number 13 were given to isprime() this would imply that the digits 1 and 3 are adjacent somewhere in the grid, which would in turn imply that the prime number 131 is in the grid so the program will find 131 before ever getting to 13. The primes 2, 3, 5 and 7 are dealt with specially at the end of the main() routine. STAGE 2: Stage 2 performs a Miller test, which will decide either that n is composite or that n is prime or strongly pseudoprime to the base 2. In the latter case, the test proceeds to stage 3. The composite number n is pseudoprime to the base b if b^(n-1) = 1 (mod n). By Fermat's Little Theorem, this equation holds if n is prime (and n does not divide b). Unfortunately it can't be used definitively for a primality test as it also holds for some composite numbers; these are the so-called pseudoprimes. Miller's test first writes n-1 as 2^s*t where t is odd. Then n passes Miller's test to the base b if either b^t = 1 (mod n) or b^(2^j*t) = -1 (mod n) for some j in {0,...,s-1}. All primes pass Miller's test to the base b (again provided n does not divide b); composite numbers that pass the test are said to be strongly pseudoprime to the base b. There are only 1282 composite numbers less than a billion that are strongly pseudoprime to the base 2 and of these only 1069 have smallest factor larger than the 40th prime, 173. If the Miller test to the base 2 fails then the number is either prime or one of these 1069 composite numbers. To complete the test we could go on to do a Miller-3 test (Miller test to the base 3), which only 55 composite numbers will still pass, a Miller-5 test, which only 3 composite numbers will still pass and a Miller-7 test, which no composite number less than a billion passes. The 3 composite numbers that slip through the Miller-2, Miller-3 and Miller-5 tests are 25326001, 161304001 and 960946321. Fred ruled early on that it was not legitimate to test explicitly for these composite numbers, hence apparently requiring four Miller tests in the case of the prime number. Actually much more can be said. It can be shown that most of the 1282 numbers that pass the Miller-2 test will never be handed to the prime testing routine. This is because for many of them, one can prove that if that number is in the grid then a larger prime is also in the grid and therefore will have been discovered already. In fact, if we exclude these from the list of 1282, (and exclude those with smallest factor no larger than 173), we are left with only these 5: 265020001 826004467 844545271 888868441 902566501 Of these, the last two might indeed appear (one can give grids), and the other three are still in question. Since we can't explicitly test for these five numbers, but since none passes the Miller-3 test, we are led to: STAGE 3: Stage 3 performs a Miller-3 test. This will only be done once, for the prime number (unless it's one of the five numbers above). */ /* It turns out the the most computationally intensive part of the Miller test is computing r*r%n where n is the number being tested and r is some number less than n. Because n can be almost one billion, integer arithmetic will probably overflow if r*r%n is used directly. The SQUARE macro uses some floating-point manipulation to do the computation, and is quite fast on the Sun, presumably because of the floating-point hardware. */ #define SQUARE \ r1 = r>>8; \ r2 = r&0xff; \ r3 = (r<<1) - r2; \ d = r1*r1; \ q = (d+0.5)*ninv; \ d = (d-nn*q)*65536.0 + r3*r2; \ q = (d+0.5)*ninv; \ r = d-nn*q; #define HIGHBIT 0x80000000 isprime(n) { register int s, ss, i, ii, r, rr, r2, q, *ip; register unsigned t, tt; double nn, ninv, r1, r3, d; /* STAGE 1: divisibilty by small primes. */ nn = n; ip = 1 + (int *)&d; for(i = 5; i < TABSIZE; i++) { d = nn * Pi[i]; if((*(ip) & 0x000fff00) == 0) return 0; } /* STAGE 2: Miller-2 test. Decompose n-1 as 2^s*t */ t = n-1; s = -1; while((t&1) == 0) { t >>= 1; s++; } /* We wish to compute r=b^t (b=2 in the first Miller test here). We do this by starting with r=1 and successively squaring it for each bit in the binary representation of t, starting with the high bit. Also, r is multiplied by b after it is squared, whenever the bit is 1. Squaring is done by the SQUARE macro given earlier. Doubling (b=2) can be done by multiplying by 2 (since two billion is still less than the largest integer) and subtracting n if necessary. The preliminary loop below shifts t left until its high bit appears as the most significant bit, and i keeps track of how many bits are left to shift out of t. Also, we remember the values of s, t and i in case we have to go on to the Miller-3 test later. */ i = 32; while((t&HIGHBIT) == 0) { t <<= 1; i--; } ss = s; tt = t; ii = i; r = 1; /* This little computation does the first few squarings (and possible doublings) of r in one step, since the fancy code is not needed until r gets too big to square as an integer. */ if(i >= 4) { r = 1<<(t>>28); if(r >= n) r %= n; t <<= 4; i -= 4; } /* Now do the squaring and doubling for each bit in t. */ ninv = 1.0/nn; while(i--) { SQUARE if(t&HIGHBIT) if((r <<= 1) >= n) r -= n; t <<= 1; } /* This is the actual Miller-2 test; is r now either 1 (mod n) or is it or one of its successive squares -1 (mod n)? */ if(r != 1 && r != n-1) while(s-- > 0) { SQUARE if(r == n-1) break; } /* If the number fails the Miller-2 test, it must be composite and we can return. Otherwise, we must go on to the Miller-3 test. */ if(s < 0) return 0; /* STAGE 3: Miller-3 test. This is almost identical to the previous code, the only difference being that we are computing 3^t this time, and so trebling instead of doubling for each 1-bit of t. */ s = ss; t = tt; i = ii; r = 1; while(i--) { SQUARE if(t&HIGHBIT) { rr = r; if((r <<= 1) >= n) r -= n; if((r += rr) >= n) r -= n; } t <<= 1; } if(r != 1 && r != n-1) while(s-- > 0) { SQUARE if(r == n-1) break; } if(s < 0) return 0; /* must be prime! */ return 1; }