You're given *Q* queries of the form (*L*, *R*). 

For each query you have to find the number of such *x* that *L* ≤ *x* ≤ *R* and there exist integer numbers *a* &gt; 0, *p* &gt; 1 such that *x* = *a*<sup class="upper-index">*p*</sup>.
The first line contains the number of queries *Q* (1 ≤ *Q* ≤ 10<sup class="upper-index">5</sup>).

The next *Q* lines contains two integers *L*, *R* each (1 ≤ *L* ≤ *R* ≤ 10<sup class="upper-index">18</sup>).
In query one the suitable numbers are 1 and 4.
6
1 4
9 9
5 7
12 29
137 591
1 1000000
2
1
0
3
17
1111
20
862 928
758 964
541 789
622 943
328 900
14 764
217 972
461 847
442 468
900 986
518 529
938 993
549 851
690 944
484 601
320 910
98 868
816 915
765 880
551 770
1
4
5
6
14
32
20
9
0
2
1
1
6
4
4
15
26
2
2
4
# -*- coding: utf - 8 -*-
"""""""""""""""""""""""""""""""""""""""""""""
|    author: mr.math - Hakimov Rahimjon     |
|    e-mail: [email protected]          |
|    created: 23.03.2018 21:09              |
"""""""""""""""""""""""""""""""""""""""""""""
# inp = open("input.txt", "r"); input = inp.readline; out = open("output.txt", "w"); print = out.write
TN = int(input())


# ===========================================


def solution():
    from math import log
    l, r = map(int, input().split())
    ans = 0
    lst = [1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000, 1024, 1089, 1156, 1225, 1296, 1331, 1369, 1444, 1521, 1600, 1681, 1728, 1764, 1849, 1936, 2025, 2116, 2197, 2209, 2304, 2401, 2500, 2601, 2704, 2744, 2809, 2916, 3025, 3125, 3136, 3249, 3364, 3375, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 4913, 5041, 5184, 5329, 5476, 5625, 5776, 5832, 5929, 6084, 6241, 6400, 6561, 6724, 6859, 6889, 7056, 7225, 7396, 7569, 7744, 7776, 7921, 8000, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9261, 9409, 9604, 9801, 10000, 10201, 10404, 10609, 10648, 10816, 11025, 11236, 11449, 11664, 11881, 12100, 12167, 12321, 12544, 12769, 12996, 13225, 13456, 13689, 13824, 13924, 14161, 14400, 14641, 14884, 15129, 15376, 15625, 15876, 16129, 16384, 16641, 16807, 16900, 17161, 17424, 17576, 17689, 17956, 18225, 18496, 18769, 19044, 19321, 19600, 19683, 19881, 20164, 20449, 20736, 21025, 21316, 21609, 21904, 21952, 22201, 22500, 22801, 23104, 23409, 23716, 24025, 24336, 24389, 24649, 24964, 25281, 25600, 25921, 26244, 26569, 26896, 27000, 27225, 27556, 27889, 28224, 28561, 28900, 29241, 29584, 29791, 29929, 30276, 30625, 30976, 31329, 31684, 32041, 32400, 32761, 32768, 33124, 33489, 33856, 34225, 34596, 34969, 35344, 35721, 35937, 36100, 36481, 36864, 37249, 37636, 38025, 38416, 38809, 39204, 39304, 39601, 40000, 40401, 40804, 41209, 41616, 42025, 42436, 42849, 42875, 43264, 43681, 44100, 44521, 44944, 45369, 45796, 46225, 46656, 47089, 47524, 47961, 48400, 48841, 49284, 49729, 50176, 50625, 50653, 51076, 51529, 51984, 52441, 52900, 53361, 53824, 54289, 54756, 54872, 55225, 55696, 56169, 56644, 57121, 57600, 58081, 58564, 59049, 59319, 59536, 60025, 60516, 61009, 61504, 62001, 62500, 63001, 63504, 64000, 64009, 64516, 65025, 65536, 66049, 66564, 67081, 67600, 68121, 68644, 68921, 69169, 69696, 70225, 70756, 71289, 71824, 72361, 72900, 73441, 73984, 74088, 74529, 75076, 75625, 76176, 76729, 77284, 77841, 78400, 78961, 79507, 79524, 80089, 80656, 81225, 81796, 82369, 82944, 83521, 84100, 84681, 85184, 85264, 85849, 86436, 87025, 87616, 88209, 88804, 89401, 90000, 90601, 91125, 91204, 91809, 92416, 93025, 93636, 94249, 94864, 95481, 96100, 96721, 97336, 97344, 97969, 98596, 99225, 99856, 100000, 100489, 101124, 101761, 102400, 103041, 103684, 103823, 104329, 104976, 105625, 106276, 106929, 107584, 108241, 108900, 109561, 110224, 110592, 110889, 111556, 112225, 112896, 113569, 114244, 114921, 115600, 116281, 116964, 117649, 118336, 119025, 119716, 120409, 121104, 121801, 122500, 123201, 123904, 124609, 125000, 125316, 126025, 126736, 127449, 128164, 128881, 129600, 130321, 131044, 131769, 132496, 132651, 133225, 133956, 134689, 135424, 136161, 136900, 137641, 138384, 139129, 139876, 140608, 140625, 141376, 142129, 142884, 143641, 144400, 145161, 145924, 146689, 147456, 148225, 148877, 148996, 149769, 150544, 151321, 152100, 152881, 153664, 154449, 155236, 156025, 156816, 157464, 157609, 158404, 159201, 160000, 160801, 161051, 161604, 162409, 163216, 164025, 164836, 165649, 166375, 166464, 167281, 168100, 168921, 169744, 170569, 171396, 172225, 173056, 173889, 174724, 175561, 175616, 176400, 177241, 178084, 178929, 179776, 180625, 181476, 182329, 183184, 184041, 184900, 185193, 185761, 186624, 187489, 188356, 189225, 190096, 190969, 191844, 192721, 193600, 194481, 195112, 195364, 196249, 197136, 198025, 198916, 199809, 200704, 201601, 202500, 203401, 204304, 205209, 205379, 206116, 207025, 207936, 208849, 209764, 210681, 211600, 212521, 213444, 214369, 215296, 216000, 216225, 217156, 218089, 219024, 219961, 220900, 221841, 222784, 223729, 224676, 225625, 226576, 226981, 227529, 228484, 229441, 230400, 231361, 232324, 233289, 234256, 235225, 236196, 237169, 238144, 238328, 239121, 240100, 241081, 242064, 243049, 244036, 245025, 246016, 247009, 248004, 248832, 249001, 250000, 250047, 251001, 252004, 253009, 254016, 255025, 256036, 257049, 258064, 259081, 260100, 261121, 262144, 263169, 264196, 265225, 266256, 267289, 268324, 269361, 270400, 271441, 272484, 273529, 274576, 274625, 275625, 276676, 277729, 278784, 279841, 280900, 281961, 283024, 284089, 285156, 286225, 287296, 287496, 288369, 289444, 290521, 291600, 292681, 293764, 294849, 295936, 297025, 298116, 299209, 300304, 300763, 301401, 302500, 303601, 304704, 305809, 306916, 308025, 309136, 310249, 311364, 312481, 313600, 314432, 314721, 315844, 316969, 318096, 319225, 320356, 321489, 322624, 323761, 324900, 326041, 327184, 328329, 328509, 329476, 330625, 331776, 332929, 334084, 335241, 336400, 337561, 338724, 339889, 341056, 342225, 343000, 343396, 344569, 345744, 346921, 348100, 349281, 350464, 351649, 352836, 354025, 355216, 356409, 357604, 357911, 358801, 360000, 361201, 362404, 363609, 364816, 366025, 367236, 368449, 369664, 370881, 371293, 372100, 373248, 373321, 374544, 375769, 376996, 378225, 379456, 380689, 381924, 383161, 384400, 385641, 386884, 388129, 389017, 389376, 390625, 391876, 393129, 394384, 395641, 396900, 398161, 399424, 400689, 401956, 403225, 404496, 405224, 405769, 407044, 408321, 409600, 410881, 412164, 413449, 414736, 416025, 417316, 418609, 419904, 421201, 421875, 422500, 423801, 425104, 426409, 427716, 429025, 430336, 431649, 432964, 434281, 435600, 436921, 438244, 438976, 439569, 440896, 442225, 443556, 444889, 446224, 447561, 448900, 450241, 451584, 452929, 454276, 455625, 456533, 456976, 458329, 459684, 461041, 462400, 463761, 465124, 466489, 467856, 469225, 470596, 471969, 473344, 474552, 474721, 476100, 477481, 478864, 480249, 481636, 483025, 484416, 485809, 487204, 488601, 490000, 491401, 492804, 493039, 494209, 495616, 497025, 498436, 499849, 501264, 502681, 504100, 505521, 506944, 508369, 509796, 511225, 512000, 512656, 514089, 515524, 516961, 518400, 519841, 521284, 522729, 524176, 525625, 527076, 528529, 529984, 531441, 532900, 534361, 535824, 537289, 537824, 538756, 540225, 541696, 543169, 544644, 546121, 547600, 549081, 550564, 551368, 552049, 553536, 555025, 556516, 558009, 559504, 561001, 562500, 564001, 565504, 567009, 568516, 570025, 571536, 571787, 573049, 574564, 576081, 577600, 579121, 580644, 582169, 583696, 585225, 586756, 588289, 589824, 591361, 592704, 592900, 594441, 595984, 597529, 599076, 600625, 602176, 603729, 605284, 606841, 608400, 609961, 611524, 613089, 614125, 614656, 616225, 617796, 619369, 620944, 622521, 624100, 625681, 627264, 628849, 630436, 632025, 633616, 635209, 636056, 636804, 638401, 640000, 641601, 643204, 644809, 646416, 648025, 649636, 651249, 652864, 654481, 656100, 657721, 658503, 659344, 660969, 662596, 664225, 665856, 667489, 669124, 670761, 672400, 674041, 675684, 677329, 678976, 680625, 681472, 682276, 683929, 685584, 687241, 688900, 690561, 692224, 693889, 695556, 697225, 698896, 700569, 702244, 703921, 704969, 705600, 707281, 708964, 710649, 712336, 714025, 715716, 717409, 719104, 720801, 722500, 724201, 725904, 727609, 729000, 729316, 731025, 732736, 734449, 736164, 737881, 739600, 741321, 743044, 744769, 746496, 748225, 749956, 751689, 753424, 753571, 755161, 756900, 758641, 759375, 760384, 762129, 763876, 765625, 767376, 769129, 770884, 772641, 774400, 776161, 777924, 778688, 779689, 781456, 783225, 784996, 786769, 788544, 790321, 792100, 793881, 795664, 797449, 799236, 801025, 802816, 804357, 804609, 806404, 808201, 810000, 811801, 813604, 815409, 817216, 819025, 820836, 822649, 824464, 826281, 828100, 829921, 830584, 831744, 833569, 835396, 837225, 839056, 840889, 842724, 844561, 846400, 848241, 850084, 851929, 853776, 855625, 857375, 857476, 859329, 861184, 863041, 864900, 866761, 868624, 870489, 872356, 874225, 876096, 877969, 879844, 881721, 883600, 884736, 885481, 887364, 889249, 891136, 893025, 894916, 896809, 898704, 900601, 902500, 904401, 906304, 908209, 910116, 912025, 912673, 913936, 915849, 917764, 919681, 921600, 923521, 925444, 927369, 929296, 931225, 933156, 935089, 937024, 938961, 940900, 941192, 942841, 944784, 946729, 948676, 950625, 952576, 954529, 956484, 958441, 960400, 962361, 964324, 966289, 968256, 970225, 970299, 972196, 974169, 976144, 978121, 980100, 982081, 984064, 986049, 988036, 990025, 992016, 994009, 996004, 998001, 1000000, 1030301, 1048576, 1061208, 1092727, 1124864, 1157625, 1185921, 1191016, 1225043, 1259712, 1295029, 1331000, 1336336, 1367631, 1404928, 1419857, 1442897, 1481544, 1500625, 1520875, 1560896, 1601613, 1643032, 1679616, 1685159, 1728000, 1771561, 1815848, 1860867, 1874161, 1889568, 1906624, 1953125, 2000376, 2048383, 2085136, 2097152, 2146689, 2197000, 2248091, 2299968, 2313441, 2352637, 2406104, 2460375, 2476099, 2515456, 2560000, 2571353, 2628072, 2685619, 2744000, 2803221, 2825761, 2863288, 2924207, 2985984, 3048625, 3111696, 3112136, 3176523, 3200000, 3241792, 3307949, 3375000, 3418801, 3442951, 3511808, 3581577, 3652264, 3723875, 3748096, 3796416, 3869893, 3944312, 4019679, 4084101, 4096000, 4100625, 4173281, 4251528, 4330747, 4410944, 4477456, 4492125, 4574296, 4657463, 4741632, 4826809, 4879681, 4913000, 5000211, 5088448, 5153632, 5177717, 5268024, 5308416, 5359375, 5451776, 5545233, 5639752, 5735339, 5764801, 5832000, 5929741, 6028568, 6128487, 6229504, 6250000, 6331625, 6434856, 6436343, 6539203, 6644672, 6751269, 6765201, 6859000, 6967871, 7077888, 7189057, 7301384, 7311616, 7414875, 7529536, 7645373, 7762392, 7880599, 7890481, 7962624, 8000000, 8120601, 8242408, 8365427, 8489664, 8503056, 8615125, 8741816, 8869743, 8998912, 9129329, 9150625, 9261000, 9393931, 9528128, 9663597, 9765625, 9800344, 9834496, 9938375, 10077696, 10218313, 10360232, 10503459, 10556001, 10648000, 10793861, 10941048, 11089567, 11239424, 11316496, 11390625, 11543176, 11697083, 11852352, 11881376, 12008989, 12117361, 12167000, 12326391, 12487168, 12649337, 12812904, 12960000, 12977875, 13144256, 13312053, 13481272, 13651919, 13824000, 13845841, 13997521, 14172488, 14348907, 14526784, 14706125, 14776336, 14886936, 15069223, 15252992, 15438249, 15625000, 15752961, 15813251, 16003008, 16194277, 16387064, 16581375, 16777216, 16974593, 17173512, 17210368, 17373979, 17576000, 17779581, 17850625, 17984728, 18191447, 18399744, 18609625, 18821096, 18974736, 19034163, 19248832, 19465109, 19683000, 19902511, 20123648, 20151121, 20346417, 20511149, 20570824, 20796875, 21024576, 21253933, 21381376, 21484952, 21717639, 21952000, 22188041, 22425768, 22665187, 22667121, 22906304, 23149125, 23393656, 23639903, 23887872, 24010000, 24137569, 24300000, 24389000, 24642171, 24897088, 25153757, 25411681, 25412184, 25672375, 25934336, 26198073, 26463592, 26730899, 26873856, 27000000, 27270901, 27543608, 27818127, 28094464, 28372625, 28398241, 28629151, 28652616, 28934443, 29218112, 29503629, 29791000, 29986576, 30080231, 30371328, 30664297, 30959144, 31255875, 31554496, 31640625, 31855013, 32157432, 32461759, 32768000, 33076161, 33362176, 33386248, 33554432, 33698267, 34012224, 34328125, 34645976, 34965783, 35153041, 35287552, 35611289, 35937000, 36264691, 36594368, 36926037, 37015056, 37259704, 37595375, 37933056, 38272753, 38614472, 38950081, 38958219, 39135393, 39304000, 39651821, 40001688, 40353607, 40707584, 40960000, 41063625, 41421736, 41781923, 42144192, 42508549, 42875000, 43046721, 43243551, 43614208, 43986977, 44361864, 44738875, 45118016, 45212176, 45435424, 45499293, 45882712, 46268279, 46656000, 47045881, 47437928, 47458321, 47832147, 48228544, 48627125, 49027896, 49430863, 49787136, 49836032, 50243409, 50653000, 51064811, 51478848, 51895117, 52200625, 52313624, 52521875, 52734375, 53157376, 53582633, 54010152, 54439939, 54700816, 54872000, 55306341, 55742968, 56181887, 56623104, 57066625, 57289761, 57512456, 57960603, 58411072, 58863869, 59319000, 59776471, 59969536, 60236288, 60466176, 60698457, 61162984, 61629875, 62099136, 62570773, 62742241, 63044792, 63521199, 64000000, 64481201, 64964808, 65450827, 65610000, 65939264, 66430125, 66923416, 67419143, 67917312, 68417929, 68574961, 68921000, 69343957, 69426531, 69934528, 70444997, 70957944, 71473375, 71639296, 71991296, 72511713, 73034632, 73560059, 74088000, 74618461, 74805201, 75151448, 75686967, 76225024, 76765625, 77308776, 77854483, 78074896, 78402752, 78953589, 79235168, 79507000, 80062991, 80621568, 81182737, 81450625, 81746504, 82312875, 82881856, 83453453, 84027672, 84604519, 84934656, 85184000, 85766121, 86350888, 86938307, 87528384, 88121125, 88529281, 88716536, 89314623, 89915392, 90224199, 90518849, 91125000, 91733851, 92236816, 92345408, 92959677, 93576664, 94196375, 94818816, 95443993, 96059601, 96071912, 96702579, 97336000, 97972181, 98611128, 99252847, 99897344, 100000000, 100544625, 101194696, 101847563, 102400000, 102503232, 103161709, 103823000, 104060401, 104487111, 105154048, 105823817, 106496424, 107171875, 107850176, 108243216, 108531333, 109215352, 109902239, 110592000, 111284641, 111980168, 112550881, 112678587, 113379904, 114084125, 114791256, 115501303, 115856201, 116214272, 116930169, 116985856, 117649000, 118370771, 119095488, 119823157, 120553784, 121287375, 121550625, 122023936, 122763473, 123505992, 124251499, 125000000, 125751501, 126247696, 126506008, 127263527, 128024064, 128787625, 129554216, 130323843, 130691232, 131079601, 131096512, 131872229, 132651000, 133432831, 134217728, 135005697, 135796744, 136048896, 136590875, 137388096, 138188413, 138991832, 139798359, 140608000, 141158161, 141420761, 142236648, 143055667, 143877824, 144703125, 145531576, 146363183, 146410000, 147008443, 147197952, 148035889, 148877000, 149721291, 150568768, 151419437, 151807041, 152273304, 153130375, 153990656, 154854153, 155720872, 156590819, 157351936, 157464000, 158340421, 159220088, 160103007, 160989184, 161878625, 162771336, 163047361, 163667323, 164566592, 164916224, 165469149, 166375000, 167284151, 168196608, 168896016, 169112377, 170031464, 170953875, 171879616, 172808693, 173741112, 174676879, 174900625, 175616000, 176558481, 177504328, 178453547, 179406144, 180362125, 181063936, 181321496, 182284263, 183250432, 184220009, 184528125, 185193000, 186169411, 187149248, 187388721, 188132517, 189119224, 190109375, 191102976, 192100033, 193100552, 193877776, 194104539, 195112000, 196122941, 197137368, 198155287, 199176704, 200201625, 200533921, 201230056, 202262003, 203297472, 204336469, 205379000, 205962976, 206425071, 207360000, 207474688, 208527857, 209584584, 210644875, 211708736, 212776173, 213847192, 214358881, 214921799, 216000000, 217081801, 218167208, 219256227, 220348864, 221445125, 221533456, 222545016, 223648543, 224755712, 225866529, 226981000, 228099131, 228886641, 229220928, 229345007, 230346397, 231475544, 232608375, 233744896, 234885113, 236029032, 236421376, 237176659, 238328000, 239483061, 240641848, 241804367, 242970624, 244140625, 245314376, 246491883, 247673152, 248858189, 250047000, 251239591, 252047376, 252435968, 253636137, 254803968, 254840104, 256047875, 257259456, 258474853, 259694072, 260144641, 260917119, 262144000, 263374721, 264609288, 265847707, 267089984, 268336125, 268435456, 269586136, 270840023, 272097792, 273359449, 274625000, 275894451, 276922881, 277167808, 278445077, 279726264, 281011375, 282300416, 282475249, 283593393, 284890312, 285610000, 286191179, 287496000, 288804781, 290117528, 291434247, 292754944, 294079625, 294499921, 295408296, 296740963, 298077632, 299418309, 300763000, 302111711, 303464448, 303595776, 304821217, 306182024, 307546875, 308915776, 310288733, 311665752, 312500000, 312900721, 313046839, 314432000, 315821241, 317214568, 318611987, 320013504, 321419125, 322417936, 322828856, 324242703, 325660672, 327082769, 328509000, 329939371, 331373888, 332150625, 332812557, 334255384, 335702375, 337153536, 338608873, 340068392, 341532099, 342102016, 343000000, 344472101, 345025251, 345948408, 347428927, 348913664, 350402625, 351895816, 352275361, 353393243, 354894912, 356400829, 357911000, 359425431, 360944128, 362467097, 362673936, 363994344, 365525875, 367061696, 368601813, 370146232, 371694959, 373248000, 373301041, 374805361, 376367048, 377933067, 379503424, 380204032, 381078125, 382657176, 384160000, 384240583, 385828352, 387420489, 389017000, 390617891, 392223168, 393832837, 395254161, 395446904, 397065375, 398688256, 400315553, 401947272, 403583419, 405224000, 406586896, 406869021, 408518488, 410172407, 411830784, 413493625, 415160936, 416832723, 418161601, 418195493, 418508992, 420189749, 421875000, 423564751, 425259008, 426957777, 428661064, 429981696, 430368875, 432081216, 433798093, 435519512, 437245479, 438976000, 440711081, 442050625, 442450728, 444194947, 445943744, 447697125, 449455096, 451217663, 452984832, 454371856, 454756609, 456533000, 458314011, 459165024, 460099648, 461889917, 463684824, 465484375, 466948881, 467288576, 469097433, 470910952, 472729139, 474552000, 476379541, 478211768, 479785216, 480048687, 481890304, 483736625, 485587656, 487443403, 489303872, 491169069, 492884401, 493039000, 494913671, 496793088, 498677257, 500566184, 502459875, 503284375, 504358336, 506250000, 506261573, 508169592, 510082399, 512000000, 513922401, 515849608, 517781627, 519718464, 519885601, 521660125, 523606616, 525557943, 527514112, 529475129, 531441000, 533411731, 533794816, 535387328, 537367797, 539353144, 541343375, 543338496, 545338513, 547343432, 547981281, 549353259, 550731776, 551368000, 553387661, 555412248, 557441767, 559476224, 561515625, 562448656, 563559976, 565609283, 567663552, 569722789, 571787000, 573856191, 575930368, 577200625, 578009537, 580093704, 582182875, 584277056, 586376253, 588480472, 590589719, 592240896, 592704000, 594823321, 596947688, 599077107, 601211584, 601692057, 603351125, 605495736, 607573201, 607645423, 609800192, 611960049, 614125000, 616295051, 618470208, 620650477, 622835864, 623201296, 625026375, 627222016, 629422793, 631628712, 633839779, 636056000, 638277381, 639128961, 640503928, 642735647, 644972544, 647214625, 649461896, 651714363, 653972032, 655360000, 656234909, 656356768, 658503000, 660776311, 663054848, 665338617, 667627624, 669921875, 671898241, 672221376, 674526133, 676836152, 679151439, 681472000, 683797841, 686128968, 688465387, 688747536, 690807104, 693154125, 695506456, 697864103, 700227072, 702595369, 704969000, 705911761, 707347971, 709732288, 712121957, 714516984, 714924299, 716917375, 719323136, 721734273, 723394816, 724150792, 726572699, 729000000, 731432701, 733870808, 736314327, 738763264, 741200625, 741217625, 743677416, 746142643, 748613312, 751089429, 753571000, 756058031, 758550528, 759333136, 761048497, 763551944, 766060875, 768575296, 771095213, 773620632, 776151559, 777600000, 777796321, 778688000, 781229961, 783777448, 786330467, 788889024, 791453125, 794022776, 796594176, 796597983, 799178752, 801765089, 804357000, 806954491, 809557568, 812166237, 814780504, 815730721, 817400375, 820025856, 822656953, 825293672, 827936019, 830584000, 833237621, 835210000, 835896888, 838561807, 841232384, 843908625, 844596301, 846590536, 849278123, 851971392, 854670349, 855036081, 857375000, 860085351, 862801408, 865523177, 868250664, 870983875, 873722816, 875213056, 876467493, 879217912, 881974079, 884736000, 887503681, 890277128, 893056347, 895745041, 895841344, 898632125, 901428696, 904231063, 907039232, 909853209, 912673000, 915498611, 916132832, 916636176, 918330048, 921167317, 924010424, 926859375, 929714176, 932574833, 935441352, 937890625, 938313739, 941192000, 944076141, 946966168, 949862087, 952763904, 955671625, 958585256, 959512576, 961504803, 964430272, 967361669, 970299000, 973242271, 976191488, 979146657, 981506241, 982107784, 985074875, 988047936, 991026973, 992436543, 994011992, 997002999, 1000000000, 1003875856, 1026625681, 1049760000, 1073283121, 1073741824, 1097199376, 1121513121, 1146228736, 1160290625, 1171350625, 1196883216, 1222830961, 1249198336, 1252332576, 1275989841, 1291467969, 1303210000, 1330863361, 1350125107, 1358954496, 1387488001, 1416468496, 1445900625, 1453933568, 1475789056, 1506138481, 1536953616, 1544804416, 1564031349, 1568239201, 1600000000, 1632240801, 1664966416, 1680700000, 1698181681, 1731891456, 1766100625, 1800814096, 1804229351, 1836036801, 1838265625, 1871773696, 1908029761, 1934917632, 1944810000, 1982119441, 2019963136, 2058346161, 2073071593, 2097273616, 2136750625, 2176782336, 2217373921, 2219006624, 2258530576, 2300257521, 2342560000, 2373046875, 2385443281, 2428912656, 2472973441, 2517630976, 2535525376, 2562890625, 2565726409, 2608757776, 2655237841, 2702336256, 2706784157, 2750058481, 2798410000, 2847396321, 2887174368, 2897022976, 2947295521, 2998219536, 3010936384, 3049800625, 3077056399, 3102044416, 3154956561, 3208542736, 3262808641, 3276800000, 3317760000, 3373402561, 3429742096, 3486784401, 3518743761, 3544535296, 3603000625, 3662186256, 3707398432, 3722098081, 3782742016, 3844124001, 3906250000, 3939040643, 3969126001, 4032758016, 4096000000, 4097152081, 4162314256, 4182119424, 4228250625, 4294967296, 4362470401, 4430766096, 4437053125, 4499860561, 4569760000, 4640470641, 4704270176, 4711998736, 4750104241, 4784350561, 4857532416, 4931550625, 4984209207, 5006411536, 5082121521, 5158686976, 5236114321, 5277319168, 5314410000, 5393580481, 5473632256, 5489031744, 5554571841, 5584059449, 5636405776, 5719140625, 5802782976, 5887339441, 5904900000, 5972816656, 6059221281, 6146560000, 6234839521, 6240321451, 6321363049, 6324066576, 6414247921, 6505390336, 6590815232, 6597500625, 6690585616, 6784652161, 6879707136, 6956883693, 6975757441, 7072810000, 7170871761, 7256313856, 7269949696, 7339040224, 7370050801, 7471182096, 7573350625, 7676563456, 7737809375, 7780827681, 7886150416, 7992538801, 8100000000, 8153726976, 8208541201, 8303765625, 8318169616, 8428892481, 8540717056, 8587340257, 8653650625, 8767700496, 8882874001, 8999178496, 9039207968, 9116621361, 9235210000, 9354951841, 9474296896, 9475854336, 9509900499, 9597924961, 9721171216, 9845600625, 9971220736, 10000000000, 10098039121, 10226063376, 10355301121, 10485760000, 10510100501, 10617447681, 10750371856, 10779215329, 10884540241, 11019960576, 11040808032, 11156640625, 11294588176, 11433811041, 11574317056, 11592740743, 11716114081, 11859210000, 12003612721, 12149330176, 12166529024, 12230590464, 12296370321, 12444741136, 12594450625, 12745506816, 12762815625, 12897917761, 13051691536, 13206836241, 13363360000, 13382255776, 13521270961, 13680577296, 13841287201, 14003408896, 14025517307, 14166950625, 14331920656, 14498327281, 14666178816, 14693280768, 14835483601, 15006250000, 15178486401, 15352201216, 15386239549, 15527402881, 15625000000, 15704099856, 15882300625, 16062013696, 16105100000, 16243247601, 16426010896, 16610312161, 16796160000, 16850581551, 16983563041, 17172529936, 17363069361, 17555190016, 17596287801, 17623416832, 17748900625, 17944209936, 18141126721, 18339659776, 18424351793, 18539817921, 18741610000, 18945044881, 19150131456, 19254145824, 19356878641, 19565295376, 19770609664, 19775390625, 19987173376, 20113571875, 20200652641, 20415837456, 20632736881, 20851360000, 21003416576, 21071715921, 21293813776, 21517662721, 21743271936, 21924480357, 21970650625, 22164361129, 22199808016, 22430753361, 22663495936, 22877577568, 22898045041, 23134410000, 23372600161, 23612624896, 23854493601, 23863536599, 24098215696, 24343800625, 24591257856, 24794911296, 24840596881, 24883200000, 25091827216, 25344958401, 25600000000, 25856961601, 25937424601, 26115852816, 26376683281, 26639462656, 26904200625, 27027081632, 27170906896, 27439591201, 27680640625, 27710263296, 27982932961, 28153056843, 28257610000, 28534304241, 28813025536, 29093783761, 29316250624, 29376588816, 29661450625, 29948379136, 30237384321, 30517578125, 30528476176, 30821664721, 30840979456, 31116960000, 31414372081, 31713911056, 31757969376, 32015587041, 32319410176, 32625390625, 32933538576, 33038369407, 33243864241, 33556377856, 33871089681, 34188010000, 34296447249, 34359738368, 34507149121, 34828517376, 35152125121, 35477982736, 35723051649, 35806100625, 36136489216, 36469158961, 36804120336, 37129300000, 37141383841, 37480960000, 37822859361, 38068692544, 38167092496, 38513670001, 38579489651, 38862602496, 39213900625, 39567575056, 39923636481, 40074642432, 40282095616, 40642963201, 41006250000, 41371966801, 41615795893, 41740124416, 42110733681, 42180533641, 42483805456, 42859350625, 43204003424, 43237380096, 43617904801, 44000935696, 44386483761, 44774560000, 44840334375, 45165175441, 45558341136, 45954068161, 46352367616, 46525874176, 46656000000, 46753250625, 47156728336, 47562811921, 47971512576, 48261724457, 48382841521, 48796810000, 49213429281, 49632710656, 50049003168, 50054665441, 50479304976, 50906640625, 51336683776, 51520374361, 51769445841, 51888844699, 52204938256, 52643172481, 53084160000, 53527912321, 53782400000, 53974440976, 54423757521, 54875873536, 55330800625, 55730836701, 55788550416, 56249134561, 56712564736, 56800235584, 57178852641, 57648010000, 57735339232, 58120048561, 58594980096, 59072816401, 59553569296, 59797108943, 60037250625, 60523872256, 61013446081, 61505984016, 61917364224, 62001498001, 62500000000, 62523502209, 63001502001, 63506016016, 64013554081, 64097340625, 64524128256, 65037750625, 65554433296, 66074188401, 66338290976, 66597028096, 67122964561, 67652010000, 68184176641, 68641485507, 68719476736, 69257922561, 69799526416, 70344300625, 70892257536, 71008211968, 71443409521, 71997768976, 72555348321, 73116160000, 73439775749, 73680216481, 74247530256, 74818113841, 75391979776, 75418890625, 75937500000, 75969140625, 76549608976, 77133397441, 77720518656, 78310985281, 78502725751, 78904810000, 79502005521, 80102584576, 80706559921, 81136812032, 81313944336, 81924750625, 82538991616, 82653950016, 83156680161, 83777829136, 83841135993, 84402451441, 85030560000, 85662167761, 86297287696, 86617093024, 86935932801, 87578116096, 88223850625, 88873149456, 89466096875, 89526025681, 90182492416, 90458382169, 90842562801, 91506250000, 92173567201, 92389579776, 92844527616, 93519144481, 94197431056, 94879400625, 95388992557, 95565066496, 96254442001, 96947540496, 97644375361, 98344960000, 98465804768, 98867482624, 99049307841, 99757432336, 100469346961, 101185065216, 101621504799, 101904600625, 102627966736, 103355177121, 104086245376, 104821185121, 104857600000, 105560010000, 106302733681, 107049369856, 107799932241, 107918163081, 108175616801, 108554434576, 109312890625, 110075314176, 110841719041, 111577100832, 111612119056, 112386528081, 113164960000, 113947428721, 114733948176, 115063617043, 115524532321, 116319195136, 117117950625, 117649000000, 117920812816, 118636749824, 118727795761, 119538913536, 120354180241, 121173610000, 121997216961, 122298103125, 122825015296, 123657019201, 124493242896, 125333700625, 126049300576, 126178406656, 127027375281, 127880620816, 128100283921, 128738157601, 129600000000, 129891985607, 130466162401, 131336659216, 132211504881, 133090713856, 133827821568, 133974300625, 134862279696, 135754665601, 136651472896, 137552716161, 137858491849, 138458410000, 139314069504, 139368569041, 140283207936, 141202341361, 141985700000, 142125984016, 143054150625, 143986855936, 144924114721, 145865941776, 146211169851, 146812351921, 147763360000, 148718980881, 149679229456, 150536645632, 150644120641, 151334226289, 151613669376, 152587890625, 153566799376, 154550410641, 154963892093, 155538739456, 156531800881, 157529610000, 158532181921, 159494694624, 159539531776, 160551674721, 161568625936, 162590400625, 163617014016, 164130859375, 164206490176, 164648481361, 165684817936, 166726039041, 167772160000, 168823196161, 168874213376, 169879162896, 170940075601, 172005949696, 173076800625, 173726604657, 174152643856, 175233494881, 176319369216, 177410282401, 177978515625, 178506250000, 178689902368, 179607287601, 180713410816, 181824635281, 182940976656, 183765996899, 184062450625, 185189072896, 186320859201, 187457825296, 188599986961, 188956800000, 189747360000, 190899960241, 192057803536, 192699928576, 193220905761, 194264244901, 194389282816, 195562950625, 196741925136, 197926222321, 199115858176, 199690286432, 200310848721, 201511210000, 202716958081, 203928109056, 205144679041, 205236901143, 206366684176, 207594140625, 208422380089, 208827064576, 210065472241, 210906087424, 211309379856, 212558803681, 213813760000, 215074265121, 216340335376, 216699865625, 217611987121, 218889236736, 220172100625, 221460595216, 222620278176, 222754736961, 224054542336, 225199600704, 225360027841, 226671210000, 227988105361, 228669389707, 229310730496, 230639102001, 231973236496, 233313150625, 234658861056, 234849287168, 236010384481, 237367737616, 238730937201, 240100000000, 241162079949, 241474942801, 242855782416, 243087455521, 244242535681, 245635219456, 247033850625, 247609900000, 248438446096, 249849022801, 251265597696, 252688187761, 254116810000, 254194901951, 255551481441, 256992219136, 258439040161, 259891961616, 260919263232, 261351000625, 262144000000, 262816174336, 264287499921, 265764994576, 267248675521, 267785184193, 268738560000, 270234665281, 271737008656, 273245607441, 274760478976, 274794888224, 276281640625, 277809109776, 279342903841, 280883040256, 281950621875, 282429536481, 283982410000, 285541678321, 287107358976, 288679469521, 289254654976, 290258027536, 291843050625, 293434556416, 295032562561, 296637086736, 296709280757, 298248146641, 299865760000, 301489944561, 303120718096, 304006671424, 304316815968, 304758098401, 306402103296, 308052750625, 309710058256, 311374044081, 312079600999, 313044726016, 314722122001, 316406250000, 318097128001, 319794774016, 320000000000, 321499206081, 323210442256, 324928500625, 326653399296, 326940373369, 328080401001, 328385156401, 330123790096, 331869318561, 333621760000, 335381132641, 336323216032, 337147454736, 338920744561, 340701020416, 342488300625, 344282603536, 344730881243, 346083947521, 347892350976, 349707832321, 351298031616, 351530410000, 353305857024, 353360102481, 355196928256, 357040905841, 358892053776, 360750390625, 362050628125, 362615934976, 364488705441, 366368720656, 368255999281, 370150560000, 370967703776, 372052421521, 373961602576, 375878121921, 377149515625, 377801998336, 379733250625, 380059617807, 381671897616, 383617958161, 385571451136, 387532395441, 389328928768, 389500810000, 391476713761, 393460125696, 395451064801, 397449550096, 398778220049, 399455600625, 401469235456, 403490473681, 404567235136, 405519334416, 407555836801, 408410100000, 409600000000, 411651843201, 413711385616, 415778646481, 417853645056, 418227202051, 419936400625, 422026932496, 424125260001, 426231402496, 428232184832, 428345379361, 430467210000, 432596913841, 433626201009, 434734510336, 436880018961, 438427732293, 439033459216, 441194850625, 443364212736, 445541565121, 447726927376, 448816553824, 449920319121, 452121760000, 454331269681, 456548867856, 458774574241, 459401384375, 461008408576, 463250390625, 464404086784, 465500540176, 467758877041, 470025421056, 470184984576, 472300192081, 474583210000, 476874494721, 479174066176, 481170140857, 481481944321, 483798149136, 486122700625, 488455618816, 490796923761, 492359665568, 493146635536, 495504774241, 496981290961, 497871360000, 500246412961, 502629953296, 503756397099, 505022001201, 507422576896, 509831700625, 512249392656, 514675673281, 515363200000, 517110562816, 519554081601, 522006250000, 524467088401, 526936617216, 527182965101, 529414856881, 531441000000, 531901827856, 534397550625, 536902045696, 539218609632, 539415333601, 541937434896, 544468370161, 547008160000, 549556825041, 551473077343, 552114385936, 554680863361, 557256278016, 559840650625, 562434001936, 563949338624, 565036352721, 567647723776, 567869252041, 570268135921, 572897610000, 575536166881, 576650390625, 578183827456, 580840612641, 583506543376, 586181640625, 588865925376, 589579257376, 591559418641, 594262141456, 596974114881, 599695360000, 602425897921, 602738989907, 605165749776, 606355001344, 607914936721, 610673479936, 613441400625, 616132666368, 616218720016, 619005459361, 621801639936, 624607283041, 627422410000, 629763392149, 630247042161, 633081200896, 635924907601, 638778183696, 641641050625, 643634300000, 644513529856, 646990183449, 647395642881, 650287411216, 653188856401, 656100000000, 657748550151, 659020863601, 661951468816, 664891837281, 667841990656, 670801950625, 672109330432, 673771738896, 676751377201, 679740887296, 682740290961, 685749610000, 686719856393, 688768866241, 689869781056, 691798081536, 694837277761, 697886476816, 700945700625, 701583371424, 704014971136, 707094310321, 710183740176, 713283282721, 716392960000, 716703146875, 719512794081, 722642807056, 725783021041, 728933458176, 732082482176, 732094140625, 735091890625, 735265090576, 738446330241, 741637881856, 744839767681, 747724704957, 748052010000, 751274631121, 754507653376, 757751099121, 761004990736, 763633171168, 764269350625, 767544201216, 770829564961, 774125464336, 777431921841, 779811265199, 780748960000, 782757789696, 784076601361, 787414868496, 790763784001, 794123370496, 796262400000, 797493650625, 800874647056, 804266382481, 807668879616, 811082161201, 812990017201, 814506250000, 817941168801, 821386940416, 824843587681, 828311133456, 829997587232, 831789600625, 832972004929, 835279012096, 838779390801, 842290759696, 845813141761, 847288609443, 849346560000, 852891037441, 856446597136, 860013262161, 863591055616, 864866612224, 867180000625, 870780120336, 874391437921, 878013976576, 881647759521, 882735153125, 885292810000, 885842380864, 888949151281, 892616806656, 896295799441, 899986152976, 900897818976, 903687890625, 907401035776, 911125611841, 914861642256, 918609150481, 919358226007, 922368160000, 926138694321, 929920776976, 933714431521, 937519681536, 938120019968, 941336550625, 941480149401, 945165062416, 949005240561, 952857108736, 956720690641, 957186876249, 960596010000, 964483090561, 968381956096, 972292630401, 976215137296, 976562500000, 980149500625, 984095744256, 988053892081, 992023968016, 996005996001, 996250626251, 1000000000000, 1016255020032, 1036579476493, 1057227821024, 1061520150601, 1078203909375, 1099511627776, 1121154893057, 1126162419264, 1143137652768, 1165463885299, 1188137600000, 1194052296529, 1211162837301, 1234543668832, 1258284197543, 1265319018496, 1282388557824, 1306860915625, 1331705468576, 1340095640625, 1356926446107, 1382528109568, 1408514752349, 1418519112256, 1434890700000, 1461660310351, 1488827973632, 1500730351849, 1516398112593, 1544375182624, 1572763671875, 1586874322944, 1601568101376, 1630793025157, 1660443030368, 1677100110841, 1690522737399, 1721036800000, 1751989905401, 1771561000000, 1783386774432, 1815232161643, 1847530855424, 1870414552161, 1880287678125, 1913507486176, 1947195170207, 1973822685184, 1981355655168, 2015993900449, 2051114900000, 2081951752609, 2086723682451, 2122825311232, 2159424884693, 2194972623936, 2196527536224, 2234138434375, 2272262782976, 2310905821257, 2313060765625, 2350072823968, 2389769101499, 2430000000000, 2436396322816, 2470770901501, 2512087224032, 2553954421743, 2565164201769, 2596377985024, 2639363440625, 2682916351776, 2699554153024, 2727042318307, 2771746976768, 2817036000549, 2839760855281, 2862915100000, 2909390022551, 2956466552832, 2985984000000, 3004150512793, 3052447761824, 3101364196875, 3138428376721, 3150905752576, 3201078401357, 3251888153568, 3297303959104, 3303341057599, 3355443200000, 3408200705601, 3461619737632, 3462825991689, 3515706497843, 3570467226624, 3625908203125, 3635215077376, 3682035745376, 3738856210407, 3796375994368, 3814697265625, 3854601532649, 3913539300000, 3973195810651, 4001504141376, 4033577618432, 4094691316893, 4156543539424, 4195872914689, 4219140959375, 4282490290176, 4346598285457, 4398046511104, 4411471739168, 4477117485699, 4543542400000, 4608273662721, 4610753397701, 4678757435232, 4747561509943, 4817172660224, 4826809000000, 4887597965625, 4958844546976, 5030919566507, 5053913144281, 5103830227968, 5177583776749, 5252187500000, 5289852801024, 5327648726751, 5403974828032, 5481173216993, 5534900853769, 5559251349024, 5638216721875, 5718076875776, 5789336458816, 5798839393557, 5880511900768, 5963102065799, 6046617600000, 6053445140625, 6131066257801, 6216455836832, 6302794178043, 6327518887936, 6390089165824, 6478348728125, 6567580836576, 6611856250609, 6657793506607, 6748994797568, 6841192812849, 6906762437184, 6934395700000, 7028611650851, 7123848901632, 7212549413161, 7220115733093, 7317420470624, 7415771484375, 7515177189376, 7529536000000, 7615646045657, 7717186558368, 7819807277899, 7858047974841, 7923516800000, 8028323765901, 8134236862432, 8198418170944, 8241264822143, 8349416423424, 8458700490625, 8550986578849, 8569125894176, 8680701550707, 8793436423168, 8907339520949, 8916100448256, 9022419900000, 9138686662951, 9256148959232, 9294114390625, 9374815985193, 9494696984224, 9615801246875, 9685390482496, 9738138110976, 9861716961757, 9986547231968, 10090298369529, 10112638401999, 10240000000000, 10368641602001, 10498572832032, 10509215371264, 10629803362243, 10762342913024, 10896201253125, 10942526586601, 11031388199776, 11167913618807, 11305787424768, 11390625000000, 11445019581049, 11585620100000, 11727599043051, 11853911588401, 11870966520832, 12015732693293, 12161907769824, 12309502009375, 12332795428864, 12458525720576, 12608989261857, 12760903041568, 12827693806929, 12914277518099, 13069123200000, 13225450646101, 13339032325696, 13383270465632, 13542593318343, 13703429914624, 13865791015625, 13867245015625, 14029687433376, 14195130030907, 14362129722368, 14412774445056, 14530697473149, 14700844300000, 14872581271151, 14976071831449, 15045919506432, 15220870177393, 15397444507424, 15557597153344, 15575653771875, 15755509298176, 15937022465957, 16120204707168, 16157819263041, 16305067506199, 16491622400000, 16679880978201, 16777216000000, 16869854883232, 17061555810443, 17254995508224, 17416274304961, 17450185778125, 17647138474976, 17845865507007, 18046378835968, 18075490334784, 18248690477249, 18452812500000, 18658757027251, 18755369578009, 18866536236032, 19076162357493, 19287647677024, 19456426971136, 19501004534375, 19716245323776, 19933382494057, 20152428548768, 20179187015625, 20373396046299, 20596297600000, 20821145878301, 20924183895616, 21047953604832, 21276733558543, 21507498573824, 21691961596369, 21740261540625, 21975035404576, 22211833167107, 22450667885568, 22483074023424, 22691552673349, 22934500700000, 23179525191351, 23298085122481, 23426639429632, 23675856753593, 23927190558624, 24137569000000, 24180654296875, 24436261477376, 24694025666157, 24953960486368, 25002110044521, 25216079618399, 25480396800000, 25746925826401, 25892303048704, 26015680550432, 26286674882643, 26559922791424, 26808753332089, 26835438303125, 27113235502176, 27393328531207, 27675731591168, 27752076864576, 27960458941449, 28247524900000, 28536943843451, 28722900390625, 28828730207232, 29122898485693, 29419463232224, 29718439059375, 29721861554176, 30019840638976, 30323682702257, 30629980039968, 30749609024289, 30938747502499, 31250000000000, 31563752502501, 31806802621504, 31880020040032, 32198817702743, 32520160641024, 32844064065625, 32894113444921, 33170543247776, 33499613519307, 33831290272768, 34012224000000, 34165588961549, 34502525100000, 34842114263551, 35161828327081, 35184372088832, 35529314273793, 35876956577824, 36227314821875, 36343632130624, 36580404888576, 36936242722357, 37294844329568, 37558352909169, 37656225778599, 38020403200000, 38387392786601, 38757210793632, 38806720086016, 39129873538843, 39505397402624, 39883798828125, 40089475140625, 40265094321376, 40649300451407, 41036433850368, 41407371740736, 41426511213649, 41819549300000, 42215564931651, 42614574994432, 42761175875209, 43016596437893, 43421646275424, 43829741584375, 44151665987584, 44240899506176, 44655137246457, 45072472075168, 45492921326699, 45579633110361, 45916502400000, 46343232758701, 46773129931232, 47045881000000, 47206211510943, 47642495156224, 48081998590625, 48524739602976, 48551226272641, 48970736047507, 49420005843968, 49872566977749, 50096498540544, 50328437500000, 50787635527751, 51250179244032, 51682540549249, 51716086897993, 52185376805024, 52658067346875, 53134176971776, 53310208315456, 53613724194557, 54096727596768, 54583205826799, 54980371265625, 55073177600000, 55566661698801, 56063676972832, 56564242339043, 56693912375296, 57068376781824, 57576099353125, 58087429172576, 58451728309129, 58602385427607, 59120987373568, 59643254333849, 60169205700000, 60254729561664, 60698860931851, 61232239557632, 61769361174093, 62103840598801, 62310245446624, 62854912109375, 63403380965376, 63955671886657, 64000000000000, 64511804814368, 65071799758899, 65635676800000, 65944160601201, 66203456086901, 66775157838432, 67350802343143, 67930409959424, 67937289638464, 68514001115625, 69101596310176, 69693216111707, 69980368892329, 70288881159168, 70888612161949, 71492429900000, 72074394832896, 72100355223951, 72712409055232, 73328612386193, 73948986280224, 74220378765625, 74573551871875, 75202330366976, 75835343042757, 76419346977856, 76472611247968, 77114156402999, 77760000000000, 78410163603001, 78672340886049, 79064668848032, 79723537443243, 80386791169024, 80980417183744, 81054451878125, 81726541495776, 82403082019807, 83084095520768, 83344647990241, 83769604142049, 84459630100000, 85154195684051, 85766121000000, 85853323256832, 86557035254293, 87265354185824, 87978302634375, 88245939632761, 88695903256576, 89418178782857, 90145152017568, 90785223184384, 90876845839099, 91613283200000, 92354487127101, 93100480721632, 93385106978409, 93851287159343, 94606929690624, 95367431640625, 96046742518336, 96132816409376, 96903107471907, 97678328378368, 98458502754149, 98771297640625, 99243654300000, 100033806792151, 100828984082432, 101559956668416, 101629210098393, 102434508843424, 103244904396875, 104060420914176, 104413920565969, 104881082626957, 105706913843168, 106537938947199, 107334407093824, 107374182400000, 108215668739201, 109062422579232, 109914468611443, 110322650964681, 110771831604224, 111634536403125, 112502607930976, 113376071188007, 113379904000000, 114254951251968, 115139273278249, 116029062500000, 116507435287321, 116924344228251, 117825143852032, 118731486838493, 119643398733024, 119706531338304, 120560905159375, 121484031819776, 122412804495057, 122978496247489, 123347249044768, 124287391407299, 125233257600000, 126184873719301, 126324651851776, 127142265940832, 128105460519543, 129074483789824, 129746337890625, 130049362165625, 131030122140576, 132016790288107, 133009393261568, 133244912166976, 134007957794349, 135012510700000, 136023078872351, 136821750708889, 137039689285632, 138062368994593, 139091145134624, 140126044921875, 140478247931904, 141167095653376, 142214324707157, 143267759542368, 144215816802121, 144327427699399, 145393356800000, 146465574547401, 147544108726432, 148035889000000, 148628987203643, 149720237927424, 150817888928125, 151921968318176, 151939915084881, 153032504292207, 154149525127168, 155273059182449, 155929364660224, 156403134900000, 157539780804451, 158683025503232, 159832897686693, 160005726539569, 160989426128224, 162152639684375, 163322567294976, 164170508913216, 164499237983257, 165682680855968, 166872925103499, 168070000000000, 168425239515625, 169273934903501, 170484759256032, 171702502583743, 172771465793536, 172927194497024, 174158864690625, 175397542943776, 176643259120307, 177210755074809, 177896043168768, 179155925122549, 180422935100000, 181697103304551, 181744694737984, 182978460024832, 184267035634793, 185562860593824, 186374892382561, 186865965446875, 188176380824576, 189494137443357, 190819266105568, 191102976000000, 192151797699599, 193491763200000, 194839193667601, 195930594145441, 196194120249632, 197556574179843, 198926586778624, 200304189453125, 200859416110144, 201689413697376, 203082291092407, 204482853306368, 205891132094649, 207307159300000, 208730966852651, 210162586770432, 211027453382656, 211602051158893, 213049392211424, 214504642209375, 215967833522176, 216270112515625, 217438998607457, 218918170011168, 220405380367699, 221620863468096, 221900662400000, 223404048919701, 224915572827232, 226435267111943, 227081481823729, 227963164852224, 229499299215625, 231043703458976, 232596410928507, 232653764952064, 234157455059968, 235726869378749, 237304687500000, 238339532186001, 238890943128751, 240485670060032, 242088902178993, 243700673461024, 244140625000000, 245321017971875, 246949969867776, 248587563395557, 250058907189001, 250233832892768, 251888812787799, 253552537600000, 255225041939801, 256096265048064, 256906360508832, 258596528100043, 260295579597824, 262003549978125, 262254607552729, 263720474308576, 265446387748607, 267181325549568, 268535866540096, 268925323054849, 270678415700000, 272440639012851, 274212028613632, 274941996890625, 275992620215093, 277782449622624, 279581552734375, 281389965541376, 281474976710656, 283207724127657, 285034864670368, 286871423439899, 288136807515649, 288717436800000, 290572941207901, 292437973214432, 294312569464143, 294929514414144, 296196766695424, 298090601740625, 299994111526176, 301855146292441, 301907333072707, 303830303495168, 305763060002949, 307705639900000, 308915776000000, 309658080584951, 311620419551232, 313592694387193, 315574942776224, 316113500535561, 317567202496875, 319569511422976, 321581907523757, 323450441233984, 323604428863968, 325637113603999, 327680000000000, 329733126404001, 330928743953809, 331796531264032, 333870253124243, 335954330625024, 338048802503125, 338550579265536, 340153707591776, 342269084820807, 344394973216768, 346318142640625, 346531411903049, 348678440100000, 350836097125051, 353004422392832, 354233654641216, 355183455415293, 357373235801824, 359573803259375, 361785197592576, 362299361110569, 364007458703857, 366240626593568, 368484741360099, 370517533364224, 370739843200000, 373005972408101, 375283169377632, 377571474600343, 378890468381881, 379870928666624, 382181572265625, 384503446185376, 386836591312907, 387420489000000, 389181048634368, 391536859235149, 393904064300000, 396109944105121, 396282705113151, 398672823058432, 401074459619393, 403487656379424, 404961208827904, 405912455021875, 408348897330176, 410797025187957, 413256880579168, 413976684737889, 415728505588199, 418211942400000, 420707233300201, 423158800038976, 423214420675232, 425733547012443, 428264654900224, 430807787028125, 432510009765625, 433362986186976, 435930295269007, 438509757267968, 441101415279249, 442032795979776, 443705312500000, 446321492229251, 448949997868032, 451590872919493, 451729667968489, 454244160989024, 456909905784375, 459588151115776, 461603162442304, 462278940896057, 464982319140768, 467698329968299, 470427017600000, 471655843734321, 473168426360301, 475922600676832, 478689585080543, 481469424205824, 481890304000000, 484262162790625, 487067845676576, 489886517809107, 492309163417681, 492718224237568, 495563010115349, 498420920700000, 501292001353351, 502915070389824, 504176297541632, 507073854835593, 509984718910624, 512908935546875, 513710701744969, 515846550629376, 518797610148157, 521762160198368, 524698762940416, 524740246980399, 527731916800000, 530737216068401, 533756191302432, 535881988265625, 536788889124643, 539835356263424, 542895639553125, 545969785934176, 547263141046336, 549057842453207, 552159856263168, 555275874623449, 558405944900000, 558845013849409, 561550114565451, 564708431199232, 567880942487693, 570630428688384, 571067696224224, 574268740309375, 577484122750976, 580713891664257, 582622237229761, 583958095271968, 587216781904499, 590490000000000, 593777798104501, 594823321000000, 597080224872032, 600397329064743, 603729159553024, 607075765315625, 607236591593241, 610437195439776, 613813499121307, 617204725664768, 619864990879744, 620610924483549, 624032145100000, 627468437145551, 630919850360832, 632711491215049, 634386434595793, 637868239809824, 641365316071875, 644877713560576, 645779095649856, 648405482564357, 651948673481568, 655507336820599, 659070838140625, 659081523200000, 662671283348601, 666276668105632, 669897728420843, 672589783760896, 673534515354624, 677187080078125, 680855473873376, 684539748133407, 686339028913329, 688239954362368, 691956144175649, 695688369300000, 699436681573651, 700321701542464, 703201132946432, 706981775479893, 710778661347424, 714540961348201, 714591842834375, 718421372338176, 722267302368457, 726129685547168, 729000000000000, 730008574608699, 733904022400000, 737816081880701, 741744806123232, 743702041351801, 745690248312943, 749652461748224, 753631499840625, 757627416114976, 758650341657664, 761640264209507, 765670097875968, 769716970979749, 773780937500000, 773848189788129, 777862051529751, 781960367276032, 786075939059993, 789298907447296, 790208821317024, 794359068596875, 798526735563776, 802711876996557, 805005849390625, 806914547788768, 811134802948799, 815372697600000, 819628286980801, 820972403643456, 823901626444832, 828192771461043, 832501777613824, 836828700603125, 837201991720249, 841173596244576, 845536520469607, 849917529325568, 853698068844544, 854316678975849, 858734025700000, 863169625893851, 867623536069632, 870464124169641, 872095812856093, 876586512998624, 881095693359375, 885623410917376, 887503681000000, 890169722768657, 894734686126368, 899318358320899, 903920796800000, 904820297013361, 908542059128901, 913182202990432, 917841286185143, 922417564483584, 922519366631424, 927216502365625, 931932751542176, 936668172433707, 940299110504209, 941422823431168, 946196763043949, 950990049900000, 955802742745951, 958468597212736, 960634900447232, 965486581988193, 970357846472224, 975248753121875, 976929722015625, 980159361278976, 985089730404757, 990039920079968, 995009990004999, 995686217814016, 1000000000000000, 1014741853230169, 1034100432834624, 1053765797374081, 1073741824000000, 1094032426497921, 1114641555517504, 1135573198803289, 1156831381426176, 1178420166015625, 1200343652992576, 1222605980803089, 1245211326152704, 1268163904241521, 1291467969000000, 1315127813325481, 1339147769319424, 1363532208525369, 1388285542167616, 1413412221390625, 1438916737499136, 1464803622199009, 1491077447838784, 1517742827651961, 1544804416000000, 1572266908616041, 1600135042849344, 1628413597910449, 1657107395117056, 1686221298140625, 1715760213253696, 1745729089577929, 1776132919332864, 1806976738085401, 1838265625000000, 1870004703089601, 1902199139467264, 1934854145598529, 1967974977554496, 2001566936265625, 2035635367776256, 2070185663499849, 2105223260474944, 2140753641621841, 2176782336000000, 2213314919066161, 2250357012933184, 2287914286629609, 2325992456359936, 2364597285765625, 2403734586186816, 2443410216924769, 2483630085505024, 2524400147941281, 2565726409000000, 2607614922465721, 2650071791407104, 2693103168443689, 2736715256013376, 2780914306640625, 2825706623205376, 2871098559212689, 2917096519063104, 2963706958323721, 3010936384000000, 3058791354808281, 3107278481449024, 3156404426880769, 3206175906594816, 3256599688890625, 3307682595151936, 3359431500123609, 3411853332189184, 3464955073649161, 3518743761000000, 3573226485213841, 3628410392018944, 3684302682180849, 3740910611784256, 3798241492515625, 3856302691946496, 3915101633817529, 3974645798323264, 4034942722397601, 4096000000000000, 4157825282402401, 4220426278476864, 4283810754983929, 4347986536861696, 4412961507515625, 4478743609109056, 4545340842854449, 4612761269305344, 4681013008649041, 4750104241000000, 4820043206693961, 4890838206582784, 4962497602330009, 5035029816707136, 5108443333890625, 5182746699759616, 5257948522194369, 5334057471375424, 5411082280083481, 5489031744000000, 5567914722008521, 5647740136496704, 5728516973659089, 5810254283800576, 5892961181640625, 5976646846618176, 6061320523197289, 6146991521173504, 6233669215980921, 6321363049000000, 6410082527866081, 6499837226778624, 6590636786811169, 6682490916222016, 6775409390765625, 6869402054004736, 6964478817623209, 7060649661739584, 7157924635221361, 7256313856000000, 7355827511386641, 7456475858388544, 7558269224026249, 7661218005651456, 7765332671265625, 7870623759839296, 7977101881632129, 8084777718513664, 8193662024284801, 8303765625000000, 8415099419290201, 8527674378686464, 8641501547944329, 8756592045368896, 8872957063140625, 8990607867641856, 9109555799784049, 9229812275335744, 9351388785251241, 9474296896000000, 9598548249896761, 9724154565432384, 9851127637605409, 9979479338254336, 10109221616390625, 10240366498532416, 10372926089038969, 10506912570445824, 10642338203800681, 10779215329000000, 10917556365126321, 11057373810786304, 11198680244449489, 11341488324787776, 11485810791015625, 11631660463230976, 11779050242756889, 11927993112483904, 12078502137213121, 12230590464000000, 12384271322498881, 12539558025308224, 12696463968316569, 12855002631049216, 13015187577015625, 13177032454057536, 13340550994697809, 13505757016489984, 13672664422368561, 13841287201000000, 14011639427134441, 14183735261958144, 14357588953446649, 14533214836718656, 14710627334390625, 14889840956932096, 15070870303021729, 15253730059904064, 15438435003747001, 15625000000000000, 15813440003753001, 16003770060096064, 16196005304479729, 16390160963076096, 16586252353140625, 16784294883374656, 16984304054288649, 17186295458566144, 17390284781428441, 17596287801000000, 17804320388674561, 18014398509481984, 18226538222455809, 18440755681001536, 18657067133265625, 18875488922505216, 19096037487458569, 19318729362716224, 19543581179092881, 19770609664000000, 19999831641819121, 20231264034275904, 20464923860814889, 20700828238974976, 20938994384765625, 21179439613043776, 21422181337891489, 21667237072994304, 21914624432020321, 22164361129000000, 22416464978706681, 22670953897037824, 22927845901396969, 23187159111076416, 23448911747640625, 23713122135310336, 23979808701347409, 24248989976440384, 24520684595090761, 24794911296000000, 25071688922457241, 25351036422727744, 25632972850442049, 25917517364985856, 26204689231890625, 26494507823224896, 26786992617986329, 27082163202494464, 27380039270784201, 27680640625000000, 27983987175790801, 28290098942705664, 28598996054590129, 28910698749983296, 29225227377515625, 29542602396307456, 29862844376368249, 30185973998996544, 30512012057180641, 30840979456000000, 31172897213027361, 31507786458731584, 31845668436881209, 32186564504948736, 32530496134515625, 32877484911678016, 33227552537453169, 33580720828186624, 33937011715960081, 34296447249000000, 34659049592086921, 35024841026965504, 35393843952755289, 35766080886362176, 36141574462890625, 36520347436056576, 36902422678601089, 37287823182704704, 37676572060402521, 38068692544000000, 38464207986489481, 38863141861967424, 39265517766052369, 39671359416303616, 40080690652640625, 40493535437763136, 40909917857572009, 41329862121590784, 41753392563387961, 42180533641000000, 42611309937355041, 43045746160697344, 43483867145012449, 43925697850453056, 44371263363765625, 44820588898717696, 45273699796525929, 45730621526284864, 46191379685396401, 46656000000000000, 47124508325403601, 47596930646515264, 48073293078275529, 48553621866090496, 49037943386265625, 49526284146440256, 50018670786022849, 50515130076626944, 51015688922507841, 51520374361000000, 52029213562955161, 52542233833181184, 53059462610881609, 53580927470095936, 54106656120140625, 54636676406050816, 55171016309022769, 55709703946857024, 56252767574402281, 56800235584000000, 57352136505929721, 57908499008855104, 58469351900270689, 59034724126949376, 59604644775390625, 60179143072269376, 60758248384885689, 61341990221615104, 61930398232359721, 62523502209000000, 63121332085847281, 63723917940097024, 64331289992282769, 64943478606730816, 65560514292015625, 66182427701415936, 66809249633371609, 67441011031941184, 68077742987260161, 68719476736000000, 69366243661827841, 70018075295866944, 70675003317157849, 71337059553120256, 72004275980015625, 72676684723410496, 73354318058640529, 74037208411275264, 74725388357583601, 75418890625000000, 76117748092591401, 76821993791524864, 77531660905535929, 78246782771397696, 78967392879390625, 79693524873773056, 80425212553252449, 81162489871457344, 81905390937410041, 82653950016000000, 83408201528457961, 84168180052830784, 84933920324457009, 85705457236443136, 86482825840140625, 87266061345623616, 88055199122167369, 88850274698727424, 89651323764419481, 90458382169000000, 91271485923347521, 92090671199944704, 92915974333361089, 93747431820736576, 94585080322265625, 95428956661682176, 96279097826745289, 97135540969725504, 97998323407891921, 98867482624000000, 99743056266780081, 100625082151426624, 101513598260088169, 102408642742358016, 103310253915765625, 104218470266268736, 105133330448746209, 106054873287491584, 106983137776707361, 107918163081000000, 108859988535875641, 109808653648236544, 110764198096878249, 111726661732987456, 112696084580640625, 113672506837303296, 114655968874330129, 115646511237465664, 116644174647345801, 117649000000000000, 118661028367354201, 119680300997734464, 120706859316371329, 121740744925904896, 122781999606890625, 123830665318305856, 124886784198057049, 125950398563487744, 127021550911887241, 128100283921000000, 129186640449535761, 130280663537680384, 131382396407607409, 132491882463990336, 133609165294515625, 134734288670396416, 135867296546886969, 137008233063797824, 138157142546011681, 139314069504000000, 140479058634340321, 141652154820234304, 142833403132026489, 144022848827723776, 145220537353515625, 146426514344294976, 147640825624179889, 148863517207035904, 150094635296999121, 151334226289000000, 152582336769287881, 153839013515956224, 155104303499468569, 156378253883185216, 157660912023890625, 158952325472321536, 160252541973695809, 161561609468241984, 162879576091729561, 164206490176000000, 165542400249498441, 166887355037806144, 168241403464173649, 169604594650054656, 170976977915640625, 172358602780396096, 173749518963594729, 175149776384856064, 176559425164683001, 177978515625000000, 179407098289692001, 180845223885144064, 182292943340781729, 183750307789612096, 185217368568765625, 186694177220038656, 188180785490436649, 189677245332718144, 191183608905939441, 192699928576000000, 194226256916188561, 195762646707729984, 197309150940332809, 198865822812737536, 200432715733265625, 202009883320369216, 203597379403181569, 205195258022068224, 206803573429178881, 208422380089000000, 210051732678908121, 211691686089723904, 213342295426266889, 215003616007910976, 216675703369140625, 218358613260107776, 220052401647189489, 221757124713546304, 223472838859681321, 225199600704000000, 226937467083370681, 228686495053685824, 230446741890423969, 232218265089212416, 234001122366390625, 235795371659574336, 237601071128220409, 239418279154192384, 241247054342326761, 243087455521000000, 244939541742696241, 246803372284575744, 248679006649044049, 250566504564321856, 252465925985015625, 254377331092688896, 256300780296434329, 258236334233446464, 260184053769595201, 262144000000000000, 264116234249604801, 266100818073753664, 268097813258767129, 270107281822519296, 272129286015015625, 274163888318971456, 276211151450391249, 278271138359148544, 280343912229566641, 282429536481000000, 284528074768416361, 286639590982979584, 288764149252633209, 290901813942684736, 293052649656390625, 295216721235542016, 297394093761051169, 299584832553538624, 301789003173921081, 304006671424000000, 306237903347050921, 308482765228413504, 310741323596082289, 313013645221298176, 315299797119140625, 317599846549120576, 319913861015774089, 322241908269256704, 324584056305938521, 326940373369000000, 329310927949028481, 331695788784615424, 334095024862954369, 336508705420439616, 338936899943265625, 341379678168027136, 343837110082320009, 346309265925342784, 348796216188498961, 351298031616000000, 353814783205469041, 356346542208545344, 358893380131489449, 361455368735789056, 364032580038765625, 366625086314181696, 369232960092848929, 371856274163236864, 374495101572082401, 377149515625000000, 379819589887092601, 382505398183563264, 385207014600327529, 387924513484626496, 390657969445640625, 393407457355104256, 396173052347920849, 398954829822778944, 401752865442768841, 404567235136000000, 407398015096219161, 410245281783429184, 413109111924508609, 415989582513831936, 418886770813890625, 421800754355914816, 424731610940495769, 427679418638209024, 430644255790238281, 433626201009000000, 436625333178768721, 439641731456303104, 442675475271472689, 445726644327885376, 448795318603515625, 451881578351333376, 454985504099933689, 458107176654167104, 461246677095770721, 464404086784000000, 467579487356261281, 470772960728745024, 473984589097059769, 477214454936866816, 480462641004515625, 483729230337679936, 487014306255994609, 490317952361693184, 493640252540246161, 496981290961000000, 500341152077816841, 503719920629714944, 507117681641509849, 510534520424456256, 513970522576890625, 517425773984874496, 520900360822838529, 524394369554227264, 527907886932144601, 531441000000000000, 534993796092155401, 538566362834572864, 542158788145462929, 545771160235933696, 549403567610640625, 553056099068437056, 556728843703025449, 560421890903609344, 564135330355546041, 567869252041000000, 571623746239596961, 575398903529078784, 579194814785959009, 583011571186179136, 586849264205765625, 590707985621487616, 594587827511515369, 598488882256079424, 602411242538130481, 606355001344000000, 610320251964061521, 614307087993392704, 618315603332438089, 622345892187672576, 626398049072265625, 630472168806746176, 634568346519668289, 638686677648277504, 642827257939177921, 646990183449000000, 651175550545069081, 655383455906074624, 659613996522740169, 663867269698494016, 668143373050140625, 672442404508532736, 676764462319244209, 681109645043243584, 685478051557568361, 689869781056000000, 694284933049739641, 698723607368084544, 703185904159105249, 707671923890323456, 712181767349390625, 716715535644767296, 721273330206403129, 725855252786417664, 730461405459781801, 735091890625000000, 739746811004793201, 744426269646782464, 749130369924173329, 753859215536440896, 758612910510015625, 763391559198969856, 768195266285705049, 773024136781639744, 777878276027898241, 782757789696000000, 787662783788549761, 792593364639928384, 797549638916984409, 802531713619726336, 807539696082015625, 812573693972260416, 817633815294109969, 822720168387149824, 827832861927597681, 832972004929000000, 838137706742929321, 843330077059682304, 848549225908978489, 853795263660659776, 859068301025390625, 864368449055358976, 869695819144977889, 875050523031587904, 880432672796160121, 885842380864000000, 891279760005451881, 896744923336604224, 902237984319995569, 907759056765321216, 913308254830140625, 918885693020585536, 924491486192068809, 930125749549993984, 935788598650465561, 941480149401000000, 947200518061237441, 952949821243654144, 958728175914275649, 964535699393390656, 970372509356265625, 976238723833860096, 982134461213542729, 988059840239808064, 994014980014994001, 1000000000000000000]
    for i in lst:
        if l<=i<=r: ans+=1
        elif i>r: break
    print(ans)


# ===========================================
while TN != 0:
    solution()
    TN -= 1
# ===========================================
# inp.close()
# out.close()
