题意 ：一个数能被他各个位数之和整除则符合要求，给L,R，问区间里有多少个数符合要求。
即使你不会DP，也可以分段打表，比如10w为一个区间，统计这有多少个符合要求，然后对于一个数，先判断在哪个区间，再把之前的求和，对所在的区间暴力搜。
记得打表用的函数：freopen（"E:\\out.txt","w",stdout);
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#define LL long long
#include <stdlib.h>
using namespace std;
int gsum[]={0,11871,11166,10611,10042,9549,9104,8717,8433,8098,7836,11226,10597,10102,9573,9123,8705,8345,8116,7800,7546,10653,10105,9662,9161,8748,8383,8034,7815,7531,7311,10138,9647,9250,8779,8422,8066,7736,7559,7301,7061,9689,9230,8903,8451,8109,7797,7478,7326,7056,6833,9271,8870,8594,8175,7848,7569,7276,7094,6857,6639,8897,8547,8289,7906,7610,7341,7080,6861,6678,6469,8575,8230,8021,7662,7399,7116,6875,6699,6494,6290,8223,7935,7745,7429,7171,6931,6709,6499,6292,6135,7913,7676,7494,7184,6974,6745,6550,6326,6146,5991,11191,10626,10014,9579,9116,8728,8379,8101,7827,7572,10599,10131,9555,9131,8743,8361,8034,7811,7545,7319,10116,9673,9144,8761,8410,8038,7739,7556,7286,7071,9662,9269,8782,8419,8084,7757,7466,7309,7051,6848,9253,8933,8468,8111,7823,7503,7228,7068,6840,6644,8902,8612,8196,7831,7578,7293,7007,6863,6655,6436,8568,8302,7941,7601,7334,7078,6836,6675,6447,6270,8262,8050,7693,7380,7136,6906,6656,6475,6312,6109,7971,7764,7437,7139,6938,6707,6488,6287,6129,5957,7696,7513,7206,6935,6746,6526,6341,6141,5958,5803,10631,10033,9541,9142,8751,8399,8057,7831,7590,7341,10133,9551,9114,8755,8387,8063,7754,7544,7313,7101,9694,9163,8739,8419,8068,7782,7486,7292,7087,6883,9286,8803,8411,8076,7791,7493,7228,7060,6854,6665,8942,8496,8119,7809,7537,7240,6984,6847,6623,6458,8620,8218,7881,7559,7306,7057,6795,6642,6443,6293,8324,7959,7632,7333,7098,6854,6612,6472,6286,6099,8058,7703,7417,7116,6916,6671,6448,6298,6121,5931,7785,7443,7198,6907,6695,6514,6284,6119,5934,5786,7546,7241,6985,6705,6519,6363,6130,5944,5822,5681,10034,9545,9117,8765,8405,8097,7788,7584,7361,7158,9574,9121,8715,8403,8078,7800,7502,7316,7125,6907,9171,8754,8390,8084,7791,7504,7250,7083,6897,6689,8833,8420,8071,7809,7503,7253,7004,6840,6666,6506,8515,8162,7816,7535,7270,7030,6780,6619,6467,6301,8228,7902,7573,7310,7073,6814,6598,6449,6289,6115,7975,7652,7368,7095,6870,6631,6444,6279,6075,5948,7708,7445,7175,6885,6685,6495,6280,6120,5945,5813,7477,7207,6944,6680,6522,6308,6091,5954,5813,5630,7257,6977,6770,6502,6332,6130,5968,5799,5646,5522,9538,9112,8707,8418,8118,7813,7539,7370,7161,7025,9114,8710,8350,8077,7797,7533,7273,7131,6896,6811,8760,8387,8060,7790,7506,7300,7012,6879,6702,6597,8438,8089,7762,7510,7262,7036,6769,6645,6502,6378,8153,7824,7532,7283,7028,6802,6571,6447,6264,6194,7892,7575,7308,7062,6811,6631,6396,6236,6089,6035,7654,7376,7075,6852,6652,6448,6221,6085,5935,5856,7434,7171,6907,6675,6483,6269,6085,5946,5776,5728,7192,6952,6725,6468,6295,6115,5920,5783,5629,5598,6993,6780,6547,6274,6128,5967,5767,5630,5511,5453,9121,8723,8368,8120,7840,7583,7351,7165,7036,6808,8717,8374,8027,7800,7551,7307,7059,6938,6822,6575,8395,8049,7760,7528,7299,7057,6821,6700,6604,6382,8096,7770,7512,7260,7036,6835,6583,6471,6373,6209,7834,7530,7278,7034,6816,6638,6363,6246,6199,6013,7598,7300,7055,6829,6616,6427,6202,6076,6004,5855,7377,7084,6880,6642,6430,6250,6056,5896,5835,5728,7174,6915,6689,6455,6264,6098,5915,5756,5730,5615,6965,6736,6505,6269,6101,5918,5738,5615,5573,5456,6771,6544,6352,6123,5927,5773,5632,5475,5426,5341,8741,8375,8037,7881,7591,7360,7162,7060,6805,6567,8368,8038,7748,7566,7329,7103,6907,6824,6591,6406,8070,7774,7488,7297,7086,6877,6652,6606,6388,6224,7790,7504,7233,7049,6846,6638,6408,6394,6185,6017,7530,7275,7036,6830,6636,6437,6219,6166,5991,5855,7313,7057,6848,6606,6438,6272,6027,5984,5851,5733,7120,6857,6640,6441,6237,6083,5853,5832,5739,5589,6934,6695,6478,6277,6089,5902,5729,5694,5569,5491,6726,6522,6333,6083,5895,5776,5607,5532,5443,5379,6569,6370,6159,5928,5767,5628,5446,5397,5322,5258,8397,8064,7792,7619,7395,7200,7044,6814,6626,6409,8059,7763,7473,7353,7131,6944,6797,6606,6422,6209,7766,7494,7240,7103,6892,6691,6583,6394,6220,6037,7498,7256,7010,6845,6668,6494,6351,6175,6021,5906,7274,7044,6796,6615,6485,6301,6130,6015,5865,5733,7049,6827,6611,6431,6252,6082,5955,5858,5725,5592,6839,6635,6456,6243,6073,5908,5804,5691,5582,5498,6684,6486,6300,6067,5917,5780,5639,5572,5492,5394,6519,6309,6119,5924,5774,5613,5502,5439,5358,5276,6331,6138,5991,5768,5621,5474,5410,5307,5218,5164,8084,7798,7539,7402,7187,7070,6790,6598,6417,6178,7772,7499,7275,7135,6927,6846,6583,6385,6221,6036,7507,7262,7038,6891,6706,6633,6357,6194,6067,5868,7270,7008,6776,6679,6491,6397,6147,6008,5874,5717,7035,6821,6602,6465,6275,6215,5992,5846,5726,5607,6816,6634,6422,6245,6092,6022,5794,5713,5618,5505,6643,6439,6244,6063,5919,5846,5648,5584,5486,5382,6459,6273,6099,5917,5751,5692,5538,5454,5364,5290,6268,6116,5965,5733,5604,5583,5410,5309,5266,5175,6144,5975,5802,5608,5477,5439,5298,5215,5164,5063,7815,7567,7333,7182,7079,6826,6577,6374,6216,6025,7536,7295,7070,6940,6839,6621,6364,6221,6030,5848,7277,7037,6848,6735,6605,6422,6183,6033,5876,5727,7040,6811,6618,6485,6383,6238,5984,5844,5733,5601,6846,6616,6420,6287,6217,6037,5825,5719,5591,5477,6653,6422,6244,6102,6007,5853,5696,5597,5466,5395,6423,6251,6072,5922,5838,5719,5552,5453,5367,5285,6269,6099,5904,5739,5719,5577,5404,5336,5274,5195,6116,5910,5765,5618,5560,5430,5306,5257,5157,5072,5948,5796,5657,5463,5406,5351,5213,5140,5068,4986,11210,10580,10138,9564,9099,8712,8417,8075,7804,7550,10652,10078,9677,9162,8740,8368,8104,7804,7512,7285,10137,9635,9258,8795,8392,8047,7832,7541,7273,7033,9665,9241,8908,8470,8118,7782,7577,7311,7066,6833,9253,8856,8577,8178,7849,7538,7322,7102,6851,6595,8867,8519,8271,7923,7588,7318,7120,6890,6646,6401,8531,8218,8014,7672,7373,7143,6914,6686,6508,6227,8224,7930,7729,7444,7167,6936,6723,6527,6339,6064,7918,7647,7471,7234,6957,6730,6530,6349,6151,5933,7623,7399,7225,7020,6760,6576,6371,6158,6003,5805,10598,10100,9580,9128,8711,8361,8097,7787,7532,7307,10109,9666,9173,8765,8371,8031,7827,7515,7300,7069,9657,9257,8787,8430,8075,7742,7540,7271,7052,6832,9255,8900,8477,8135,7808,7479,7318,7067,6819,6615,8878,8594,8172,7872,7548,7262,7100,6844,6637,6430,8537,8296,7910,7605,7350,7051,6878,6667,6465,6219,8248,8019,7657,7383,7131,6867,6686,6502,6294,6036,7967,7754,7437,7191,6921,6699,6530,6327,6135,5889,7686,7525,7197,6966,6741,6542,6335,6142,6000,5763,7422,7265,6956,6774,6568,6356,6175,5998,5846,5624,10111,9560,9150,8734,8378,8054,7798,7535,7324,7106,9678,9141,8780,8392,8064,7750,7525,7293,7062,6860,9274,8785,8432,8101,7759,7464,7280,7041,6823,6633,8920,8483,8131,7827,7523,7239,7067,6819,6649,6421,8610,8192,7855,7586,7305,6998,6860,6651,6451,6225,8318,7928,7592,7342,7094,6810,6660,6471,6256,6056,8031,7708,7385,7128,6885,6659,6488,6289,6110,5880,7778,7479,7160,6932,6739,6478,6305,6152,5971,5710,7535,7230,6957,6749,6543,6314,6156,5991,5811,5608,7272,7010,6739,6547,6357,6196,5991,5824,5689,5495,9554,9104,8767,8393,8068,7768,7536,7325,7096,6932,9159,8742,8436,8073,7774,7497,7282,7063,6888,6692,8798,8412,8104,7786,7510,7231,7034,6829,6659,6447,8498,8114,7847,7533,7265,7000,6844,6637,6455,6241,8218,7866,7577,7321,7034,6806,6650,6431,6280,6068,7946,7637,7334,7089,6860,6606,6462,6262,6121,5866,7719,7411,7130,6907,6684,6432,6300,6128,5943,5709,7471,7215,6944,6724,6502,6291,6150,5963,5816,5582,7243,7009,6718,6534,6354,6142,5965,5823,5679,5438,7021,6793,6532,6349,6191,5986,5831,5709,5556,5324,9104,8722,8404,8072,7798,7499,7310,7113,6921,6842,8746,8362,8097,7790,7522,7234,7067,6871,6674,6614,8406,8071,7807,7503,7252,7000,6835,6650,6455,6385,8121,7803,7548,7270,7026,6791,6611,6440,6298,6159,7892,7557,7296,7070,6820,6578,6441,6260,6103,5969,7641,7330,7092,6863,6622,6407,6267,6080,5923,5820,7429,7153,6879,6682,6463,6266,6094,5920,5795,5657,7215,6962,6685,6515,6308,6095,5949,5798,5657,5510,7002,6763,6509,6350,6135,5941,5804,5671,5503,5400,6782,6593,6327,6151,5998,5827,5680,5536,5395,5301,8707,8348,8105,7812,7549,7284,7120,6916,6803,6639,8386,8051,7801,7530,7293,7036,6874,6695,6600,6417,8056,7771,7505,7262,7051,6768,6630,6486,6370,6175,7807,7510,7296,7023,6820,6566,6452,6272,6166,5989,7573,7303,7083,6828,6624,6390,6244,6075,6004,5849,7362,7084,6851,6642,6442,6226,6064,5920,5870,5661,7150,6890,6662,6479,6274,6034,5916,5771,5717,5526,6965,6707,6511,6291,6102,5918,5781,5619,5575,5421,6782,6567,6296,6134,5972,5777,5639,5502,5469,5295,6598,6385,6127,5975,5820,5639,5529,5396,5344,5179,8368,8034,7822,7573,7318,7098,6924,6814,6606,6406,8044,7739,7540,7314,7076,6823,6710,6606,6384,6223,7766,7484,7279,7042,6826,6601,6475,6378,6184,6040,7513,7265,7037,6819,6636,6389,6243,6183,6022,5840,7302,7057,6831,6626,6437,6189,6071,6012,5852,5694,7082,6854,6657,6433,6253,6030,5899,5819,5695,5582,6898,6687,6471,6255,6100,5904,5738,5689,5589,5427,6731,6505,6276,6119,5929,5739,5619,5550,5477,5301,6547,6353,6132,5946,5775,5604,5491,5414,5331,5209,6387,6193,5965,5803,5644,5509,5367,5323,5236,5099,8035,7734,7600,7347,7126,6927,6838,6601,6392,6258,7771,7468,7321,7090,6889,6696,6598,6397,6227,6060,7494,7222,7044,6866,6658,6423,6378,6208,6022,5888,7258,7008,6840,6638,6454,6220,6193,6005,5849,5749,7059,6839,6646,6443,6278,6037,5989,5837,5729,5604,6851,6638,6435,6265,6108,5852,5824,5728,5586,5440,6663,6467,6272,6103,5925,5716,5689,5572,5477,5343,6492,6309,6111,5919,5785,5593,5547,5436,5376,5247,6348,6154,5936,5778,5644,5475,5410,5324,5252,5126,6206,6005,5799,5655,5491,5338,5315,5225,5137,5036,7775,7491,7346,7126,6960,6823,6579,6429,6209,6039,7487,7232,7105,6901,6703,6588,6403,6209,6036,5902,7237,6997,6860,6646,6492,6355,6181,6019,5879,5746,7033,6784,6631,6457,6293,6139,5977,5862,5754,5593,6842,6611,6445,6284,6096,5953,5848,5712,5588,5473,6620,6449,6264,6088,5917,5807,5701,5570,5480,5360,6456,6286,6067,5913,5787,5665,5544,5470,5386,5245,6300,6106,5920,5771,5629,5515,5425,5371,5264,5141,6120,5973,5788,5636,5483,5402,5319,5236,5163,5038,5988,5846,5655,5485,5383,5303,5200,5135,5078,4938,7499,7277,7140,6928,6848,6604,6400,6207,6014,5902,7262,7021,6907,6696,6636,6384,6198,6051,5870,5751,7018,6778,6665,6500,6391,6141,6002,5889,5721,5589,6805,6586,6475,6279,6198,5975,5847,5718,5600,5479,6640,6424,6287,6095,6038,5822,5685,5589,5487,5367,6467,6225,6071,5935,5862,5657,5560,5481,5367,5235,6272,6077,5930,5773,5707,5528,5453,5364,5263,5173,6109,5941,5764,5607,5574,5428,5330,5239,5195,5069,5964,5800,5616,5474,5456,5285,5216,5156,5070,4984,5828,5677,5508,5373,5315,5185,5118,5048,4970,4866,10641,10122,9680,9142,8728,8420,8097,7782,7522,7290,10126,9646,9266,8785,8397,8115,7800,7514,7270,7051,9673,9234,8903,8476,8106,7843,7563,7291,7013,6826,9227,8873,8577,8173,7839,7621,7348,7078,6817,6653,8851,8522,8285,7882,7595,7382,7119,6887,6619,6452,8510,8198,8017,7656,7373,7161,6909,6719,6429,6264,8177,7917,7761,7429,7144,6957,6722,6525,6256,6110,7896,7645,7536,7212,6963,6779,6542,6351,6110,5949,7625,7355,7276,7004,6762,6571,6372,6190,5965,5806,7366,7107,7039,6819,6582,6390,6222,6040,5802,5705,10087,9685,9175,8746,8370,8095,7776,7513,7290,7057,9636,9277,8802,8418,8030,7818,7527,7243,7032,6819,9232,8918,8479,8121,7792,7567,7302,7022,6832,6617,8876,8597,8185,7854,7537,7339,7099,6853,6605,6437,8528,8272,7917,7601,7297,7115,6890,6666,6408,6251,8215,8020,7666,7382,7102,6919,6703,6473,6241,6090,7936,7749,7449,7151,6934,6711,6514,6335,6074,5907,7664,7484,7249,6977,6734,6548,6353,6189,5912,5766,7400,7235,7015,6771,6551,6387,6185,5995,5797,5669,7167,7000,6794,6572,6397,6216,6028,5882,5698,5538,9661,9191,8770,8394,8044,7807,7513,7271,7073,6869,9247,8805,8441,8080,7752,7527,7252,7039,6830,6630,8915,8476,8131,7827,7484,7304,7049,6825,6600,6425,8599,8200,7862,7562,7249,7106,6862,6625,6424,6256,8299,7927,7606,7337,7048,6877,6666,6452,6248,6057,8048,7662,7384,7148,6861,6677,6493,6302,6028,5914,7758,7447,7180,6938,6664,6522,6335,6132,5884,5765,7521,7223,6981,6756,6546,6351,6155,5999,5748,5627,7291,6975,6774,6566,6367,6169,6014,5868,5612,5497,7049,6760,6600,6391,6188,6028,5889,5734,5513,5418,9140,8785,8419,8066,7767,7510,7273,7074,6864,6705,8769,8448,8102,7775,7476,7285,7027,6824,6631,6474,8474,8152,7829,7509,7241,7067,6821,6634,6438,6247,8197,7879,7581,7294,7011,6849,6639,6467,6234,6050,7938,7606,7366,7081,6803,6662,6465,6270,6045,5889,7699,7404,7145,6898,6637,6500,6288,6109,5891,5734,7468,7180,6927,6720,6494,6304,6143,5965,5720,5584,7250,6966,6768,6557,6338,6158,6009,5847,5581,5468,7016,6767,6572,6372,6170,6009,5855,5705,5489,5366,6813,6578,6370,6192,6047,5852,5714,5613,5405,5250,8726,8439,8078,7783,7492,7292,7061,6856,6723,6634,8385,8108,7786,7497,7236,7022,6818,6636,6481,6381,8114,7826,7542,7256,6993,6819,6622,6441,6239,6181,7848,7592,7320,7040,6779,6646,6428,6273,6087,6003,7612,7352,7100,6837,6593,6466,6236,6089,5901,5818,7398,7115,6902,6672,6420,6275,6103,5927,5712,5662,7188,6909,6721,6496,6261,6136,5952,5781,5572,5533,6993,6748,6537,6355,6125,5998,5817,5676,5460,5384,6794,6530,6352,6190,5973,5816,5704,5574,5343,5284,6603,6356,6193,6024,5831,5712,5567,5442,5237,5222,8367,8094,7801,7534,7261,7052,6889,6677,6615,6427,8056,7814,7516,7265,6990,6840,6647,6445,6380,6221,7803,7562,7265,7040,6780,6606,6444,6262,6189,6018,7554,7322,7063,6824,6586,6410,6264,6094,5978,5844,7332,7092,6882,6641,6386,6247,6087,5912,5811,5699,7132,6897,6678,6460,6237,6103,5903,5754,5676,5543,6945,6688,6484,6306,6089,5934,5779,5635,5511,5390,6766,6509,6349,6148,5928,5805,5672,5509,5394,5315,6606,6337,6179,5991,5797,5683,5526,5404,5301,5215,6437,6172,5993,5858,5698,5538,5433,5317,5199,5102,8038,7824,7540,7296,7056,6900,6689,6597,6435,6230,7752,7536,7267,7062,6798,6627,6475,6369,6209,6030,7499,7293,7044,6838,6570,6428,6277,6164,6001,5894,7290,7102,6833,6626,6383,6254,6075,5985,5846,5735,7084,6887,6631,6461,6217,6050,5903,5852,5678,5564,6883,6667,6468,6285,6044,5920,5770,5705,5526,5451,6704,6507,6297,6089,5890,5771,5624,5573,5406,5330,6553,6317,6144,5961,5775,5645,5486,5468,5290,5190,6395,6146,5968,5836,5640,5512,5396,5339,5188,5112,6220,5997,5849,5703,5531,5406,5284,5227,5099,5049,7735,7555,7327,7089,6856,6715,6631,6394,6232,6090,7463,7292,7083,6830,6621,6487,6375,6186,6057,5912,7262,7049,6834,6642,6402,6268,6160,6012,5884,5744,7038,6851,6634,6475,6199,6060,6015,5850,5710,5609,6841,6658,6469,6265,6035,5910,5847,5701,5568,5495,6683,6483,6265,6097,5886,5745,5692,5585,5444,5374,6499,6294,6104,5932,5743,5603,5559,5467,5304,5241,6323,6135,5979,5798,5605,5483,5452,5338,5213,5157,6183,5991,5831,5661,5519,5381,5311,5223,5120,5040,6043,5822,5688,5564,5392,5268,5217,5137,5015,4943,7473,7327,7086,6881,6709,6613,6398,6211,6065,5913,7208,7063,6852,6660,6440,6370,6183,6010,5885,5750,6993,6827,6650,6453,6217,6173,6003,5839,5731,5626,6814,6644,6465,6264,6044,5998,5827,5700,5596,5495,6646,6451,6262,6115,5857,5816,5699,5582,5464,5355,6461,6282,6111,5943,5694,5668,5601,5457,5345,5261,6301,6119,5940,5776,5569,5538,5440,5363,5246,5169,6143,5951,5773,5664,5474,5413,5315,5259,5132,5032,5994,5795,5668,5551,5339,5308,5222,5148,5020,4971,5870,5684,5545,5412,5271,5225,5111,5042,4949,4872,7230,7103,6891,6718,6594,6386,6219,6028,5886,5783,6981,6868,6673,6469,6376,6190,6024,5848,5741,5627,6784,6638,6460,6286,6160,5984,5842,5738,5599,5480,6583,6439,6276,6112,5952,5819,5713,5577,5475,5377,6425,6283,6113,5920,5781,5696,5564,5445,5372,5280,6294,6108,5933,5792,5651,5549,5447,5373,5256,5158,6115,5923,5775,5660,5507,5417,5354,5268,5140,5069,5951,5784,5664,5497,5382,5318,5237,5160,5042,4987,5828,5658,5519,5392,5305,5211,5125,5048,4952,4872,5733,5528,5397,5292,5205,5105,5052,5006,4854,4790,10141,9644,9260,8772,8435,8102,7799,7488,7266,7032,9683,9235,8901,8451,8166,7846,7542,7268,7056,6820,9267,8865,8579,8159,7908,7602,7322,7056,6843,6641,8865,8527,8263,7906,7645,7369,7135,6848,6638,6469,8483,8222,7994,7637,7445,7162,6927,6641,6475,6298,8174,7923,7733,7403,7221,6946,6721,6484,6288,6112,7866,7648,7507,7206,6993,6765,6549,6308,6123,5962,7584,7416,7272,6985,6779,6587,6391,6115,5987,5849,7326,7164,7052,6776,6607,6407,6195,6000,5867,5708,7083,6902,6829,6619,6379,6208,6058,5862,5719,5596,9666,9267,8794,8381,8111,7795,7493,7277,7031,6813,9252,8922,8478,8099,7834,7542,7277,7040,6823,6600,8872,8597,8193,7832,7593,7336,7080,6801,6641,6437,8544,8285,7907,7583,7385,7118,6874,6622,6460,6250,8215,8011,7651,7370,7167,6901,6709,6454,6252,6086,7909,7757,7417,7147,6947,6727,6533,6260,6101,5935,7637,7528,7203,6942,6781,6547,6350,6088,5964,5788,7392,7277,6997,6765,6606,6358,6191,5962,5796,5662,7117,7053,6814,6578,6387,6223,6049,5812,5709,5563,6871,6836,6606,6384,6230,6056,5886,5683,5590,5458,9289,8816,8420,8057,7799,7511,7246,7039,6828,6645,8923,8503,8128,7778,7556,7292,7020,6815,6632,6437,8610,8188,7873,7531,7331,7075,6819,6630,6430,6231,8301,7921,7618,7311,7096,6894,6657,6411,6241,6087,8018,7673,7384,7100,6914,6713,6494,6246,6085,5908,7759,7437,7155,6913,6727,6512,6327,6076,5921,5755,7508,7217,6965,6736,6538,6353,6180,5908,5756,5651,7259,7031,6780,6571,6378,6210,6019,5776,5653,5518,7012,6814,6584,6399,6238,6031,5883,5680,5550,5415,6779,6583,6400,6217,6038,5891,5757,5570,5425,5316,8840,8447,8080,7756,7525,7238,7032,6845,6634,6479,8499,8146,7823,7500,7290,7023,6817,6631,6413,6293,8203,7889,7579,7262,7086,6855,6619,6419,6252,6074,7929,7624,7351,7046,6885,6649,6459,6248,6076,5897,7693,7386,7140,6849,6685,6485,6300,6070,5893,5739,7456,7176,6937,6672,6507,6328,6142,5895,5751,5613,7242,6990,6747,6523,6357,6181,5993,5740,5629,5473,7015,6779,6571,6377,6204,6003,5882,5632,5473,5360,6786,6588,6411,6203,6028,5890,5759,5505,5373,5296,6570,6424,6209,6046,5907,5761,5623,5404,5307,5182,8455,8106,7781,7488,7250,7030,6808,6641,6485,6408,8145,7848,7504,7242,7057,6807,6610,6444,6281,6200,7879,7588,7299,7005,6853,6614,6439,6267,6068,6013,7613,7353,7091,6796,6631,6452,6262,6065,5889,5837,7381,7148,6886,6611,6484,6283,6093,5900,5762,5676,7177,6928,6707,6459,6310,6115,5937,5753,5590,5537,6964,6729,6552,6305,6142,5986,5830,5599,5453,5422,6765,6582,6373,6149,6015,5864,5702,5479,5354,5307,6577,6379,6190,6031,5875,5712,5585,5398,5261,5185,6369,6196,6030,5884,5730,5596,5495,5286,5163,5137,8130,7791,7512,7252,7032,6822,6633,6477,6407,6201,7853,7528,7280,7011,6807,6609,6445,6263,6176,6043,7591,7317,7058,6784,6624,6450,6238,6068,6019,5858,7358,7103,6837,6595,6444,6236,6087,5913,5839,5704,7129,6892,6690,6410,6268,6074,5926,5741,5674,5578,6923,6714,6510,6241,6111,5947,5775,5574,5556,5444,6738,6536,6329,6099,5971,5806,5660,5448,5411,5310,6548,6346,6187,5981,5825,5699,5567,5336,5288,5189,6360,6176,6040,5826,5705,5590,5451,5233,5207,5118,6200,6021,5873,5712,5576,5456,5329,5163,5124,5011,7829,7524,7295,7017,6822,6667,6458,6383,6219,6066,7574,7291,7034,6800,6620,6451,6242,6197,6029,5877,7341,7064,6836,6603,6410,6241,6096,5993,5851,5753,7113,6866,6653,6392,6237,6083,5917,5815,5698,5619,6913,6690,6467,6237,6073,5901,5752,5683,5568,5468,6706,6502,6287,6085,5931,5748,5617,5528,5417,5336,6519,6334,6156,5924,5791,5663,5523,5387,5301,5232,6351,6179,5980,5801,5679,5546,5397,5293,5201,5125,6184,5996,5849,5682,5553,5429,5288,5198,5106,5014,6009,5848,5731,5564,5418,5330,5210,5076,4996,4951,7546,7296,7056,6817,6659,6472,6381,6224,6038,5906,7300,7061,6855,6583,6436,6268,6173,6028,5881,5780,7101,6855,6648,6392,6272,6099,5975,5860,5762,5635,6894,6657,6458,6224,6063,5895,5831,5704,5602,5507,6692,6487,6302,6056,5901,5746,5707,5535,5453,5388,6510,6322,6131,5879,5762,5641,5553,5421,5329,5271,6352,6155,5955,5765,5651,5496,5446,5324,5224,5145,6149,5994,5850,5647,5528,5385,5373,5198,5104,5065,6002,5852,5717,5516,5417,5292,5230,5101,5020,4975,5853,5726,5587,5418,5320,5177,5128,5006,4943,4863,7289,7076,6846,6614,6485,6397,6181,6033,5918,5777,7057,6847,6625,6409,6267,6175,5985,5877,5751,5617,6837,6637,6459,6213,6052,5999,5842,5719,5607,5504,6643,6461,6294,6026,5889,5850,5679,5559,5497,5399,6500,6290,6119,5868,5748,5686,5541,5458,5368,5284,6304,6103,5959,5742,5596,5543,5445,5334,5241,5148,6126,5966,5809,5594,5465,5440,5354,5196,5152,5068,5996,5854,5680,5480,5385,5318,5230,5145,5056,4979,5838,5710,5565,5398,5271,5229,5143,5021,4961,4881,5693,5573,5443,5286,5167,5127,5044,4919,4846,4790,7069,6842,6640,6484,6375,6185,6016,5892,5748,5655,6832,6656,6452,6219,6155,6012,5842,5718,5621,5530,6638,6456,6275,6033,5997,5832,5684,5601,5489,5389,6471,6267,6101,5869,5810,5681,5555,5475,5362,5278,6275,6114,5967,5703,5664,5575,5459,5328,5256,5193,6119,5959,5799,5558,5530,5433,5340,5234,5167,5061,5986,5785,5664,5457,5407,5307,5240,5148,5060,4976,5818,5673,5546,5367,5287,5213,5167,5034,4971,4883,5687,5568,5430,5248,5217,5124,5053,4953,4899,4796,5579,5438,5312,5163,5127,5019,4945,4850,4771,4686,9670,9227,8900,8512,8126,7834,7525,7277,7041,6764,9248,8856,8579,8237,7888,7594,7312,7052,6846,6594,8866,8513,8261,7978,7648,7377,7072,6868,6662,6430,8521,8188,7981,7739,7414,7166,6902,6687,6489,6268,8175,7911,7710,7488,7188,6952,6701,6493,6301,6129,7898,7659,7474,7235,7006,6772,6506,6333,6160,5957,7606,7390,7253,7033,6807,6568,6314,6195,5974,5823,7348,7152,7041,6816,6600,6426,6168,6005,5853,5719,7097,6929,6822,6583,6418,6236,5988,5884,5748,5600,6878,6681,6614,6392,6222,6067,5839,5757,5619,5493,9241,8909,8467,8142,7828,7526,7268,7035,6812,6570,8885,8565,8177,7906,7587,7311,7053,6847,6610,6379,8535,8272,7894,7651,7354,7114,6849,6631,6454,6232,8223,7997,7635,7433,7166,6926,6669,6464,6310,6074,7951,7718,7386,7211,6948,6717,6475,6296,6118,5900,7663,7486,7184,7010,6746,6547,6319,6113,5954,5792,7403,7278,6976,6796,6593,6405,6131,5972,5827,5675,7173,7053,6775,6609,6428,6214,5993,5852,5716,5564,6910,6807,6591,6396,6237,6045,5844,5733,5566,5451,6665,6604,6402,6200,6034,5916,5719,5585,5501,5364,8908,8488,8105,7841,7531,7259,7041,6824,6592,6395,8599,8194,7839,7588,7326,7063,6824,6615,6431,6204,8288,7923,7594,7370,7118,6852,6628,6462,6252,6031,8031,7643,7366,7160,6914,6702,6447,6288,6086,5892,7754,7433,7139,6953,6702,6533,6268,6088,5937,5749,7524,7213,6930,6762,6564,6352,6101,5946,5797,5609,7289,6990,6753,6599,6374,6197,5957,5807,5650,5496,7056,6805,6579,6427,6214,6065,5829,5682,5547,5426,6814,6622,6373,6230,6070,5916,5675,5561,5463,5329,6612,6399,6198,6054,5917,5760,5563,5473,5343,5233,8501,8134,7792,7543,7291,7016,6831,6619,6450,6210,8205,7863,7542,7319,7074,6812,6643,6443,6244,6032,7925,7624,7307,7102,6866,6651,6429,6241,6070,5874,7677,7408,7099,6898,6708,6487,6258,6088,5936,5724,7454,7165,6900,6725,6523,6311,6080,5925,5758,5589,7226,6961,6729,6545,6341,6177,5931,5759,5631,5467,7017,6784,6556,6374,6196,6052,5780,5623,5522,5343,6842,6601,6392,6239,6066,5897,5673,5529,5406,5257,6607,6385,6212,6073,5898,5767,5570,5429,5293,5179,6393,6230,6054,5888,5760,5646,5433,5322,5230,5107,8152,7809,7500,7282,7011,6817,6646,6451,6274,6147,7884,7575,7258,7067,6818,6622,6436,6249,6107,5974,7625,7350,7020,6873,6655,6430,6260,6086,5910,5792,7393,7128,6855,6684,6471,6273,6095,5923,5754,5685,7169,6936,6658,6500,6303,6128,5893,5762,5632,5531,6970,6754,6475,6334,6168,5969,5752,5635,5483,5390,6772,6558,6344,6185,5995,5855,5635,5501,5354,5292,6599,6390,6199,6044,5886,5769,5523,5383,5274,5215,6411,6219,6019,5882,5764,5621,5410,5309,5168,5122,6214,6034,5865,5759,5621,5489,5318,5200,5095,5024,7840,7539,7253,7039,6818,6603,6443,6299,6222,5938,7597,7283,7027,6837,6613,6421,6278,6090,6016,5805,7360,7093,6806,6634,6440,6259,6067,5892,5858,5687,7152,6903,6612,6476,6278,6099,5903,5752,5716,5530,6926,6708,6441,6317,6117,5921,5761,5615,5543,5409,6733,6534,6306,6117,5972,5807,5611,5481,5426,5310,6556,6372,6138,5982,5848,5709,5474,5360,5319,5180,6392,6209,5996,5860,5737,5572,5388,5273,5211,5078,6203,6022,5874,5730,5590,5483,5303,5169,5116,5006,6026,5895,5730,5589,5495,5381,5184,5078,5048,4940,7549,7288,7047,6808,6609,6445,6289,6206,6045,5819,7331,7059,6809,6623,6433,6254,6072,6024,5895,5668,7102,6852,6598,6445,6249,6063,5899,5848,5725,5525,6908,6660,6432,6271,6067,5912,5751,5681,5575,5435,6717,6520,6256,6114,5930,5789,5596,5537,5458,5314,6544,6330,6071,5977,5815,5643,5461,5427,5334,5202,6348,6177,5946,5816,5673,5531,5352,5297,5214,5117,6193,6034,5841,5699,5559,5467,5248,5192,5117,5024,6037,5891,5687,5585,5463,5336,5144,5125,5029,4917,5862,5729,5592,5473,5339,5253,5079,5006,4936,4857,7314,7075,6810,6633,6462,6248,6212,6059,5907,5684,7077,6842,6607,6436,6261,6061,6033,5886,5741,5575,6875,6656,6425,6229,6084,5913,5822,5705,5623,5455,6711,6485,6224,6078,5933,5761,5679,5580,5486,5327,6523,6301,6073,5944,5757,5607,5565,5439,5347,5218,6339,6156,5922,5791,5638,5497,5427,5306,5247,5143,6193,6010,5777,5666,5535,5391,5297,5217,5142,5023,6050,5874,5679,5574,5416,5297,5205,5123,5038,4951,5868,5733,5568,5449,5329,5205,5111,5000,4948,4884,5752,5607,5446,5321,5253,5116,4983,4929,4865,4766,7057,6852,6607,6429,6268,6168,6026,5886,5778,5578,6851,6657,6406,6240,6094,5975,5844,5759,5638,5437,6649,6460,6207,6070,5912,5801,5705,5617,5489,5322,6463,6298,6057,5885,5751,5697,5553,5453,5391,5235,6320,6145,5884,5746,5626,5563,5407,5332,5275,5137,6173,5974,5741,5627,5490,5426,5297,5250,5158,5031,5995,5849,5650,5517,5359,5338,5204,5113,5066,4963,5853,5737,5537,5406,5297,5229,5117,5024,4958,4879,5735,5597,5419,5317,5200,5122,4997,4976,4875,4767,5584,5484,5332,5226,5103,5039,4946,4843,4763,4701,6854,6636,6425,6284,6175,5975,5864,5759,5636,5456,6638,6462,6225,6071,5986,5833,5737,5604,5510,5361,6453,6290,6043,5874,5829,5699,5572,5484,5397,5243,6297,6102,5857,5728,5684,5538,5437,5387,5266,5125,6117,5953,5746,5592,5531,5427,5333,5252,5172,5045,5971,5827,5627,5460,5415,5334,5203,5147,5069,4965,5843,5692,5485,5357,5333,5221,5099,5059,4988,4853,5723,5557,5399,5285,5205,5135,5025,4963,4892,4782,5577,5470,5292,5176,5123,5042,4945,4849,4785,4679,5482,5364,5188,5073,5058,4960,4843,4778,4693,4600,9242,8857,8629,8213,7875,7585,7307,7073,6776,6629,8837,8509,8338,7940,7623,7361,7087,6854,6617,6454,8508,8191,8071,7699,7417,7147,6896,6668,6470,6298,8178,7901,7804,7484,7207,6931,6705,6526,6291,6133,7875,7615,7548,7269,6970,6726,6553,6336,6131,5991,7582,7397,7297,7027,6804,6538,6370,6174,5987,5845,7352,7147,7058,6822,6625,6341,6205,6049,5872,5697,7092,6912,6828,6615,6422,6163,6034,5889,5728,5589,6859,6709,6612,6393,6228,6017,5878,5746,5623,5466,6631,6484,6375,6186,6052,5844,5734,5630,5510,5342,8857,8581,8210,7864,7588,7309,7061,6825,6589,6437,8532,8270,7964,7620,7366,7091,6842,6658,6408,6246,8206,7981,7719,7413,7135,6900,6673,6480,6249,6103,7906,7713,7497,7199,6948,6715,6495,6282,6115,5950,7651,7463,7259,6987,6780,6519,6325,6136,5962,5791,7400,7217,7031,6803,6571,6344,6171,6001,5821,5663,7151,7024,6819,6616,6397,6158,6028,5839,5696,5563,6916,6822,6611,6413,6256,6006,5865,5725,5604,5436,6707,6598,6397,6238,6076,5832,5740,5619,5482,5337,6437,6377,6205,6034,5898,5705,5597,5490,5367,5229,8602,8172,7879,7590,7296,7054,6849,6638,6362,6266,8280,7903,7636,7351,7086,6855,6642,6434,6198,6080,8008,7648,7421,7144,6914,6655,6465,6277,6065,5915,7742,7392,7209,6966,6744,6482,6282,6130,5900,5774,7496,7165,7010,6759,6539,6323,6131,5950,5767,5650,7260,6969,6799,6581,6381,6155,5973,5812,5679,5512,7068,6768,6600,6421,6234,5973,5824,5718,5547,5411,6838,6575,6433,6262,6054,5845,5721,5574,5430,5323,6606,6399,6220,6058,5922,5725,5596,5458,5364,5228,6381,6193,6010,5897,5773,5569,5476,5368,5234,5107,8207,7860,7569,7310,7054,6836,6632,6430,6214,6077,7938,7594,7350,7104,6867,6623,6446,6258,6028,5887,7668,7356,7154,6911,6682,6457,6283,6086,5861,5762,7428,7156,6950,6712,6534,6297,6094,5931,5741,5612,7213,6938,6752,6547,6369,6105,5942,5799,5619,5460,7003,6729,6603,6371,6193,5954,5820,5669,5482,5376,6804,6579,6435,6222,6054,5826,5673,5534,5396,5266,6616,6396,6233,6071,5939,5687,5556,5438,5314,5149,6422,6195,6064,5932,5782,5554,5468,5333,5204,5082,6188,6010,5887,5774,5640,5467,5360,5224,5120,4991,7885,7531,7325,7058,6803,6641,6451,6272,6025,5985,7613,7307,7098,6865,6624,6471,6253,6080,5870,5822,7401,7095,6875,6684,6484,6278,6089,5932,5728,5688,7166,6882,6707,6520,6316,6092,5941,5783,5566,5542,6954,6700,6545,6326,6150,5942,5781,5643,5460,5434,6768,6547,6359,6181,6018,5797,5639,5516,5375,5313,6579,6375,6214,6052,5892,5657,5533,5411,5253,5203,6398,6195,6076,5894,5756,5564,5423,5308,5156,5115,6211,6043,5898,5765,5632,5474,5329,5202,5096,5014,6037,5857,5725,5628,5511,5322,5225,5132,4996,4933,7584,7294,7070,6828,6620,6457,6263,6111,5964,5830,7349,7036,6858,6639,6434,6255,6081,5924,5802,5679,7146,6833,6676,6466,6255,6113,5938,5757,5641,5562,6938,6667,6491,6296,6111,5941,5785,5627,5531,5426,6759,6482,6323,6158,5976,5758,5640,5507,5394,5310,6557,6308,6174,6010,5832,5626,5516,5377,5291,5219,6384,6176,6034,5866,5735,5535,5382,5264,5195,5122,6227,6022,5879,5760,5642,5416,5292,5197,5120,4993,6043,5851,5757,5616,5511,5307,5212,5104,5014,4929,5865,5718,5611,5466,5376,5227,5106,4982,4940,4850,7296,7056,6854,6627,6431,6264,6114,6053,5780,5700,7088,6822,6652,6425,6244,6104,5914,5856,5675,5552,6914,6638,6451,6271,6095,5915,5756,5726,5552,5435,6720,6442,6294,6123,5924,5770,5634,5562,5399,5338,6538,6289,6144,5951,5783,5634,5480,5430,5300,5225,6372,6130,5981,5839,5694,5498,5350,5322,5198,5120,6208,5985,5850,5735,5583,5382,5274,5224,5073,5031,6017,5862,5739,5586,5476,5304,5179,5115,5010,4953,5885,5724,5595,5474,5388,5197,5073,5036,4941,4866,5731,5591,5458,5357,5244,5095,4976,4944,4835,4734,7091,6841,6624,6442,6260,6106,6024,5900,5689,5565,6871,6624,6441,6270,6068,5901,5876,5757,5531,5432,6678,6435,6290,6071,5904,5770,5718,5595,5425,5356,6534,6263,6113,5922,5769,5619,5544,5466,5325,5243,6359,6089,5962,5810,5646,5474,5433,5347,5192,5121,6182,5927,5834,5680,5533,5363,5323,5210,5115,5038,6048,5828,5694,5564,5466,5272,5210,5106,5031,4961,5907,5703,5578,5468,5353,5159,5121,5042,4938,4871,5754,5586,5478,5364,5225,5086,5043,4936,4862,4793,5600,5474,5367,5223,5139,4988,4937,4825,4736,4695,6852,6616,6437,6267,6065,6017,5889,5754,5553,5480,6657,6434,6236,6057,5902,5843,5710,5619,5457,5355,6501,6240,6061,5920,5747,5674,5568,5495,5330,5244,6307,6072,5911,5766,5616,5530,5453,5356,5209,5146,6155,5933,5792,5629,5482,5432,5317,5238,5127,5057,6011,5784,5644,5535,5394,5307,5205,5136,5019,4946,5868,5659,5537,5429,5283,5199,5129,5046,4932,4851,5757,5569,5447,5327,5187,5119,5033,4937,4881,4786,5639,5469,5336,5242,5120,5001,4929,4877,4777,4695,5491,5324,5220,5152,5002,4922,4840,4764,4666,4588,6666,6416,6245,6092,5982,5857,5738,5655,5461,5356,6468,6229,6068,5909,5797,5685,5602,5505,5331,5257,6275,6063,5905,5734,5663,5559,5467,5376,5229,5159,6149,5903,5738,5605,5546,5412,5337,5282,5138,5040,6000,5739,5607,5492,5430,5305,5222,5182,5017,4956,5839,5620,5502,5360,5311,5222,5139,5053,4962,4874,5738,5529,5396,5268,5238,5104,5010,4978,4866,4776,5618,5415,5308,5182,5142,5011,4943,4896,4775,4672,5502,5323,5239,5096,5031,4940,4875,4775,4682,4620,5366,5244,5116,4999,4963,4817,4748,4664,4589,4496,8852,8564,8320,7930,7638,7351,7074,6831,6650,6460,8485,8265,8048,7682,7389,7142,6900,6649,6465,6288,8146,7967,7797,7449,7179,6953,6704,6473,6329,6135,7888,7710,7556,7251,6973,6761,6544,6332,6174,6003,7586,7433,7297,7039,6739,6577,6370,6176,6011,5848,7327,7196,7064,6832,6534,6389,6219,6000,5869,5749,7089,6951,6837,6624,6369,6210,6036,5879,5724,5611,6875,6709,6612,6434,6179,6034,5914,5780,5583,5491,6614,6484,6379,6202,5974,5866,5769,5620,5456,5377,6419,6271,6186,6003,5832,5742,5612,5510,5355,5248,8497,8329,7935,7604,7352,7089,6864,6570,6438,6274,8180,8064,7684,7381,7155,6888,6665,6444,6282,6084,7893,7784,7471,7182,6933,6702,6496,6281,6107,5937,7611,7549,7256,6991,6736,6553,6340,6127,5970,5836,7361,7311,7034,6773,6544,6365,6165,5974,5841,5689,7136,7063,6834,6617,6363,6182,6007,5859,5698,5551,6896,6817,6625,6439,6152,6025,5902,5719,5574,5446,6684,6641,6409,6245,6018,5876,5750,5607,5484,5359,6479,6391,6178,6034,5853,5723,5608,5510,5355,5233,6260,6164,6011,5885,5692,5583,5499,5387,5220,5151,8279,7940,7617,7356,7101,6855,6648,6404,6246,6064,7984,7702,7402,7142,6878,6677,6478,6230,6071,5933,7701,7484,7194,6930,6700,6504,6301,6071,5943,5784,7480,7265,6991,6766,6542,6326,6139,5955,5803,5650,7227,7021,6801,6586,6345,6168,5998,5800,5665,5553,6996,6825,6634,6401,6152,6037,5833,5670,5558,5435,6798,6613,6416,6254,6003,5858,5716,5573,5455,5300,6617,6401,6252,6087,5835,5735,5617,5480,5331,5224,6374,6203,6057,5907,5682,5603,5477,5366,5245,5132,6173,6015,5871,5759,5572,5481,5367,5269,5144,5027,7915,7629,7349,7094,6857,6670,6456,6179,6076,5918,7656,7418,7124,6894,6684,6463,6283,6047,5917,5754,7420,7180,6946,6722,6481,6282,6134,5887,5748,5626,7182,7003,6767,6557,6315,6137,5970,5751,5637,5508,6965,6814,6575,6385,6176,5968,5821,5650,5532,5380,6763,6605,6420,6240,5992,5831,5709,5536,5406,5270,6571,6405,6259,6068,5826,5709,5580,5419,5291,5186,6406,6253,6092,5938,5717,5600,5453,5329,5229,5087,6202,6043,5898,5780,5590,5455,5366,5226,5125,4995,6018,5847,5767,5652,5437,5351,5271,5141,5012,4933,7600,7334,7090,6843,6664,6450,6271,6063,5900,5836,7369,7135,6897,6658,6460,6292,6098,5869,5757,5699,7138,6946,6697,6494,6295,6122,5940,5723,5624,5545,6934,6763,6526,6353,6135,5959,5804,5617,5473,5437,6721,6569,6372,6199,5967,5815,5682,5487,5354,5342,6536,6423,6205,6030,5839,5708,5544,5388,5277,5241,6371,6238,6049,5914,5701,5550,5433,5304,5162,5115,6189,6061,5925,5806,5565,5435,5356,5212,5069,5039,5997,5898,5779,5635,5429,5357,5221,5118,4996,4940,5853,5743,5605,5527,5342,5256,5144,5036,4916,4830,7322,7102,6869,6615,6463,6294,6088,5850,5822,5691,7104,6904,6672,6454,6288,6096,5927,5735,5688,5545,6889,6685,6518,6285,6105,5936,5780,5585,5540,5447,6698,6523,6358,6140,5937,5811,5649,5436,5420,5327,6529,6364,6163,6005,5824,5659,5526,5363,5319,5203,6346,6190,6031,5887,5685,5537,5439,5262,5203,5129,6166,6048,5900,5738,5549,5436,5316,5145,5120,5042,6020,5908,5764,5629,5458,5332,5195,5082,5023,4948,5875,5741,5617,5516,5334,5211,5126,5000,4919,4828,5699,5589,5518,5382,5214,5129,5041,4922,4850,4737,7076,6872,6637,6447,6274,6081,5959,5799,5671,5578,6850,6688,6489,6255,6105,5942,5781,5650,5540,5472,6669,6499,6300,6089,5938,5793,5616,5528,5437,5330,6490,6327,6137,5967,5780,5647,5511,5388,5305,5221,6307,6158,6018,5830,5648,5531,5408,5279,5185,5146,6165,6019,5856,5726,5541,5432,5283,5193,5132,5028,6011,5860,5728,5630,5421,5292,5187,5103,5010,4955,5857,5746,5630,5513,5310,5205,5096,5019,4922,4867,5702,5614,5509,5377,5218,5116,4989,4929,4843,4766,5595,5475,5363,5278,5133,5010,4903,4872,4732,4665,6866,6671,6450,6251,6112,5950,5876,5651,5540,5467,6657,6486,6279,6099,5934,5762,5736,5541,5428,5346,6454,6294,6121,5936,5787,5620,5588,5404,5327,5251,6289,6148,5968,5777,5646,5515,5436,5297,5224,5149,6151,5987,5820,5674,5520,5386,5324,5199,5130,5017,5984,5843,5735,5582,5400,5283,5247,5096,5019,4962,5856,5726,5609,5458,5301,5199,5129,4984,4951,4880,5737,5622,5485,5374,5214,5104,5047,4923,4863,4789,5576,5469,5380,5268,5107,4969,4954,4838,4737,4664,5443,5365,5287,5163,4991,4917,4865,4707,4672,4590,6639,6443,6252,6065,5898,5856,5745,5529,5449,5367,6440,6287,6097,5907,5752,5712,5598,5404,5336,5262,6267,6109,5923,5753,5622,5568,5465,5325,5244,5149,6098,5947,5780,5639,5476,5424,5350,5210,5130,5062,5920,5818,5681,5502,5359,5326,5227,5092,5022,4961,5819,5698,5563,5410,5277,5224,5128,5019,4969,4881,5712,5575,5457,5364,5163,5115,5030,4937,4858,4771,5557,5471,5359,5251,5069,5038,4963,4837,4770,4685,5462,5373,5245,5138,4977,4943,4837,4739,4694,4588,5355,5242,5141,5066,4906,4826,4730,4650,4582,4500,6448,6246,6080,5879,5842,5721,5596,5436,5359,5251,6272,6068,5907,5754,5692,5563,5482,5348,5238,5169,6067,5906,5766,5606,5530,5443,5369,5216,5139,5079,5918,5781,5622,5453,5427,5323,5242,5113,5053,4975,5800,5657,5502,5367,5315,5196,5151,5040,4934,4895,5658,5552,5427,5267,5194,5128,5042,4947,4862,4777,5537,5447,5321,5180,5112,5034,4964,4844,4778,4691,5460,5330,5218,5114,5026,4937,4859,4785,4673,4593,5331,5213,5142,5026,4911,4841,4760,4671,4587,4490,5221,5131,5043,4940,4816,4735,4664,4569,4487,4422,8553,8246,8020,7672,7422,7132,6841,6715,6486,6289,8235,7963,7765,7447,7178,6932,6683,6535,6316,6139,7932,7696,7542,7212,6984,6750,6507,6358,6162,6008,7667,7443,7310,6975,6796,6602,6343,6189,6044,5866,7415,7185,7079,6793,6590,6405,6185,6044,5888,5743,7140,6929,6848,6581,6385,6232,6054,5880,5746,5628,6893,6721,6630,6356,6192,6067,5897,5743,5633,5510,6679,6490,6390,6148,6018,5865,5732,5619,5489,5381,6456,6263,6197,5986,5847,5739,5635,5481,5353,5281,6242,6110,6019,5800,5725,5616,5508,5362,5260,5177,8248,8037,7666,7400,7123,6886,6637,6469,6275,6111,7959,7782,7437,7171,6939,6691,6480,6300,6136,5962,7703,7549,7223,6953,6770,6520,6305,6179,5974,5802,7431,7294,7036,6769,6559,6359,6163,6007,5839,5711,7172,7076,6825,6557,6396,6225,5999,5856,5734,5596,6946,6829,6616,6363,6221,6033,5863,5746,5612,5468,6723,6597,6426,6178,6033,5876,5747,5613,5483,5372,6484,6395,6221,5982,5851,5743,5609,5454,5373,5273,6287,6220,6009,5818,5728,5592,5492,5354,5266,5161,6085,6001,5873,5696,5598,5476,5411,5258,5148,5061,8052,7682,7389,7142,6900,6669,6414,6275,6111,5914,7787,7446,7168,6943,6693,6486,6264,6112,5928,5793,7527,7264,6976,6739,6516,6342,6108,5954,5805,5672,7290,7044,6783,6550,6385,6164,5957,5847,5698,5540,7069,6814,6610,6372,6198,6023,5831,5718,5557,5443,6821,6622,6427,6169,6011,5886,5724,5580,5436,5340,6611,6423,6253,5997,5873,5746,5572,5478,5367,5222,6417,6209,6057,5847,5726,5586,5461,5354,5260,5126,6182,6012,5896,5702,5572,5486,5371,5244,5125,5046,6007,5873,5739,5562,5464,5384,5259,5150,5066,4945,7693,7389,7146,6905,6653,6488,6213,6064,5931,5757,7471,7186,6932,6705,6499,6306,6060,5908,5787,5627,7257,6978,6759,6551,6327,6135,5933,5795,5633,5499,7026,6783,6600,6363,6156,5991,5804,5664,5529,5413,6815,6617,6398,6171,6023,5866,5685,5530,5435,5298,6632,6433,6239,5996,5874,5710,5554,5447,5333,5188,6414,6235,6098,5867,5717,5595,5463,5332,5216,5106,6209,6064,5933,5692,5574,5486,5336,5209,5128,5005,6034,5895,5777,5554,5472,5372,5236,5125,5039,4914,5856,5720,5653,5462,5351,5261,5186,5028,4928,4825,7402,7136,6883,6694,6498,6287,6030,5906,5758,5692,7186,6915,6714,6506,6302,6131,5899,5760,5613,5578,6976,6751,6550,6333,6128,5988,5763,5619,5505,5463,6789,6578,6349,6175,6000,5832,5648,5527,5387,5327,6608,6389,6212,6024,5832,5705,5564,5419,5275,5238,6411,6226,6067,5849,5701,5592,5439,5301,5168,5162,6232,6087,5915,5714,5596,5470,5303,5222,5120,5037,6045,5897,5784,5595,5472,5335,5223,5110,4991,4956,5853,5754,5634,5443,5349,5261,5134,5010,4919,4862,5721,5620,5518,5338,5239,5170,5039,4940,4840,4764,7124,6899,6673,6471,6303,6115,5866,5739,5672,5577,6921,6711,6484,6293,6135,5955,5709,5602,5559,5425,6744,6524,6324,6146,5980,5805,5610,5488,5430,5319,6559,6361,6200,5955,5819,5708,5499,5363,5330,5252,6400,6208,6024,5831,5703,5569,5382,5277,5235,5128,6222,6046,5882,5712,5579,5425,5293,5179,5127,5035,6047,5895,5794,5575,5456,5342,5219,5076,5003,4967,5878,5780,5653,5442,5358,5242,5106,4991,4948,4859,5732,5625,5505,5347,5248,5129,5027,4922,4845,4750,5575,5484,5395,5240,5150,5019,4955,4843,4750,4624,6902,6695,6455,6302,6130,5948,5711,5665,5543,5434,6677,6495,6305,6115,5938,5797,5585,5525,5424,5344,6515,6349,6136,5946,5803,5671,5437,5423,5331,5233,6359,6183,5997,5821,5675,5549,5337,5331,5226,5124,6187,6014,5882,5696,5536,5428,5264,5210,5123,5048,6021,5888,5757,5556,5433,5325,5145,5106,5024,4955,5893,5761,5614,5459,5347,5239,5058,5012,4963,4854,5744,5606,5497,5359,5224,5115,4998,4935,4828,4764,5585,5491,5398,5220,5126,5033,4889,4844,4750,4668,5470,5393,5281,5133,5034,4944,4802,4747,4642,4577,6694,6487,6274,6117,5947,5810,5648,5518,5442,5350,6523,6307,6101,5951,5809,5648,5504,5425,5329,5241,6333,6134,5950,5805,5667,5509,5411,5304,5223,5152,6165,6008,5845,5662,5531,5402,5286,5185,5126,5082,6021,5886,5719,5545,5432,5314,5178,5106,5047,4970,5886,5731,5605,5454,5308,5191,5098,5018,4942,4871,5735,5607,5509,5334,5213,5120,5022,4914,4853,4772,5627,5488,5395,5198,5130,5022,4927,4831,4771,4675,5512,5379,5276,5155,5027,4903,4856,4751,4652,4587,5355,5257,5186,5027,4940,4829,4731,4635,4566,4474,6482,6277,6067,5947,5788,5727,5535,5448,5343,5230,6278,6112,5922,5766,5610,5586,5422,5302,5241,5171,6132,5977,5776,5642,5510,5435,5276,5215,5146,5063,5987,5824,5657,5535,5397,5333,5177,5128,5036,4966,5848,5718,5562,5417,5280,5231,5111,5026,4957,4898,5700,5603,5464,5291,5193,5149,4981,4937,4875,4776,5608,5468,5353,5213,5106,5047,4913,4866,4768,4678,5485,5368,5263,5114,4984,4952,4834,4748,4678,4581,5356,5272,5176,5005,4909,4869,4745,4635,4584,4509,5269,5179,5065,4937,4833,4742,4630,4551,4484,4407,6277,6097,5902,5732,5716,5617,5418,5341,5267,5157,6120,5921,5735,5615,5563,5461,5301,5235,5168,5047,5936,5775,5628,5487,5425,5341,5214,5111,5040,4992,5797,5672,5522,5357,5327,5238,5092,5011,4963,4885,5692,5553,5408,5263,5227,5142,5022,4958,4872,4794,5568,5436,5322,5177,5119,5011,4951,4884,4749,4703,5444,5358,5243,5056,5022,4950,4847,4775,4703,4581,5348,5245,5140,4987,4952,4841,4740,4671,4578,4502,5266,5141,5035,4913,4855,4735,4646,4588,4498,4385,5142,5046,4974,4828,4729,4642,4560,4461,4404,4333,8200,7957,7751,7448,7186,6879,6722,6515,6331,6099,7921,7678,7506,7228,6992,6717,6547,6374,6158,5909,7640,7425,7267,7017,6768,6546,6397,6210,6009,5794,7379,7207,7048,6794,6619,6394,6225,6059,5909,5686,7145,6937,6813,6589,6416,6217,6045,5927,5781,5549,6901,6695,6577,6414,6208,6034,5902,5767,5632,5446,6651,6484,6347,6189,6025,5888,5732,5598,5513,5334,6468,6292,6118,6016,5874,5737,5603,5495,5400,5225,6281,6081,5959,5852,5717,5604,5486,5397,5269,5146,6076,5922,5794,5691,5572,5503,5357,5259,5163,5049,7945,7743,7439,7195,6923,6657,6513,6316,6108,5915,7664,7521,7221,6966,6731,6506,6351,6133,5993,5770,7429,7297,6993,6765,6588,6315,6180,6023,5869,5624,7186,7064,6790,6599,6410,6175,6053,5904,5750,5520,6930,6852,6577,6376,6213,6030,5885,5732,5630,5428,6701,6634,6364,6189,6063,5890,5745,5604,5506,5321,6498,6385,6152,6014,5877,5739,5599,5490,5374,5193,6276,6201,5968,5848,5722,5615,5485,5359,5275,5129,6098,6018,5810,5704,5596,5493,5376,5261,5185,5029,5929,5856,5649,5577,5486,5356,5250,5174,5080,4950,7760,7432,7171,6923,6715,6459,6281,6107,5955,5740,7536,7205,6971,6762,6527,6292,6148,5983,5802,5611,7294,7010,6768,6571,6340,6143,6010,5835,5695,5498,7064,6836,6577,6396,6204,6002,5867,5724,5607,5386,6844,6619,6359,6210,6055,5858,5719,5619,5476,5283,6622,6407,6182,6034,5871,5732,5607,5495,5357,5202,6374,6220,5979,5851,5737,5598,5462,5367,5247,5102,6216,6043,5806,5699,5610,5482,5336,5276,5171,4988,6035,5872,5686,5594,5469,5375,5259,5162,5058,4955,5836,5733,5552,5456,5356,5270,5156,5048,4968,4860,7437,7151,6950,6711,6511,6254,6108,5935,5768,5598,7227,6967,6748,6521,6326,6116,5942,5792,5687,5464,7025,6786,6555,6358,6175,5943,5801,5681,5556,5334,6832,6591,6389,6209,6024,5814,5714,5585,5433,5245,6619,6427,6201,6021,5875,5721,5579,5445,5347,5170,6419,6253,5992,5857,5760,5588,5470,5351,5240,5064,6219,6054,5835,5694,5591,5442,5363,5247,5123,4967,6029,5906,5706,5569,5466,5361,5239,5129,5033,4901,5869,5771,5561,5453,5378,5262,5120,5043,4973,4798,5729,5599,5443,5366,5261,5155,5044,4960,4868,4709,7156,6938,6712,6507,6324,6071,5907,5788,5635,5529,6971,6730,6550,6347,6158,5911,5789,5667,5491,5405,6769,6558,6386,6174,5982,5808,5662,5518,5400,5324,6606,6402,6191,6024,5873,5691,5543,5426,5315,5192,6418,6221,6013,5890,5736,5548,5439,5332,5216,5078,6237,6057,5864,5735,5596,5462,5358,5214,5111,5033,6047,5927,5686,5581,5472,5354,5217,5129,5018,4923,5897,5780,5559,5465,5365,5226,5128,5031,4942,4834,5740,5621,5466,5369,5254,5148,5027,4934,4825,4760,5580,5513,5345,5234,5160,5086,4944,4848,4730,4629,6929,6694,6516,6315,6132,5882,5758,5611,5533,5442,6735,6544,6332,6144,6003,5751,5623,5492,5448,5314,6572,6365,6168,6003,5865,5625,5505,5386,5325,5197,6382,6198,6030,5863,5719,5527,5425,5281,5233,5112,6209,6053,5872,5719,5583,5433,5316,5174,5146,5007,6081,5907,5707,5596,5487,5324,5210,5108,5063,4914,5903,5759,5571,5471,5345,5207,5144,4997,4946,4833,5742,5636,5472,5353,5245,5111,5018,4916,4841,4736,5621,5515,5334,5254,5162,5046,4932,4827,4776,4634,5493,5382,5219,5168,5071,4931,4871,4738,4629,4536,6724,6507,6300,6142,5969,5706,5599,5552,5422,5332,6516,6326,6156,5996,5826,5595,5480,5423,5312,5212,6342,6169,5992,5840,5696,5492,5359,5319,5224,5126,6197,6040,5843,5703,5593,5388,5247,5247,5145,5005,6041,5873,5718,5590,5460,5286,5164,5142,5046,4934,5888,5760,5595,5463,5338,5200,5098,5027,4945,4858,5750,5641,5451,5327,5255,5110,4974,4950,4864,4743,5634,5520,5336,5250,5143,5018,4912,4852,4744,4641,5469,5403,5238,5159,5039,4931,4844,4738,4629,4549,5353,5283,5132,5028,4960,4855,4731,4657,4544,4448,6509,6284,6151,5960,5808,5588,5530,5398,5321,5244,6350,6141,5974,5812,5675,5462,5401,5304,5212,5133,6188,5988,5830,5713,5561,5342,5300,5220,5130,5012,6013,5844,5718,5567,5444,5255,5220,5121,5045,4963,5878,5754,5586,5428,5348,5160,5088,5025,4970,4861,5762,5611,5471,5350,5231,5062,5012,4955,4881,4756,5617,5492,5358,5255,5127,4972,4942,4841,4757,4658,5492,5405,5249,5121,5040,4927,4838,4726,4689,4552,5405,5267,5127,5027,4941,4837,4745,4636,4566,4470,5291,5178,5036,4975,4849,4715,4654,4534,4458,4361,6330,6096,5929,5806,5654,5494,5394,5342,5229,5123,6135,5929,5811,5671,5505,5395,5317,5205,5128,5040,5992,5807,5672,5543,5403,5289,5207,5125,5057,4978,5878,5707,5527,5436,5321,5181,5090,5042,4984,4874,5724,5592,5433,5330,5189,5090,5022,4933,4875,4792,5607,5508,5349,5213,5104,5006,4930,4854,4783,4688,5490,5395,5217,5123,5005,4927,4818,4749,4686,4587,5398,5270,5127,5035,4940,4840,4734,4659,4554,4462,5260,5175,5049,4932,4813,4770,4637,4549,4495,4379,5173,5072,4946,4840,4723,4642,4542,4448,4376,4296,6093,5927,5783,5611,5585,5421,5327,5235,5140,5072,5960,5783,5643,5474,5456,5284,5211,5162,5048,4959,5826,5639,5507,5395,5325,5175,5115,5043,4957,4883,5693,5540,5405,5295,5224,5093,5034,4948,4872,4787,5583,5456,5303,5173,5157,5001,4911,4879,4793,4687,5491,5338,5210,5112,5043,4910,4855,4775,4683,4609,5352,5254,5112,4997,4952,4809,4742,4678,4564,4502,5249,5177,5017,4897,4862,4740,4633,4566,4499,4404,5192,5059,4922,4832,4770,4620,4563,4489,4383,4317,5054,4975,4857,4714,4647,4544,4441,4390,4304,4206,7896,7663,7511,7222,6927,6764,6570,6330,6127,5961,7642,7418,7265,7008,6758,6573,6384,6206,5956,5811,7377,7165,7051,6826,6571,6403,6242,6071,5808,5673,7123,6928,6835,6609,6383,6252,6080,5929,5685,5563,6893,6687,6608,6388,6220,6059,5904,5798,5572,5455,6670,6415,6390,6212,6028,5893,5761,5660,5438,5339,6457,6216,6166,6016,5854,5742,5629,5494,5355,5262,6280,6036,5996,5836,5723,5603,5487,5377,5242,5166,6108,5859,5817,5722,5602,5452,5366,5287,5141,5046,5930,5716,5700,5592,5465,5340,5271,5173,5040,4984,7673,7502,7216,6981,6694,6534,6342,6159,5939,5773,7409,7274,7003,6786,6524,6376,6193,6004,5788,5671,7175,7054,6793,6579,6374,6212,6050,5882,5681,5543,6951,6821,6589,6414,6217,6037,5901,5780,5543,5431,6704,6589,6392,6215,6030,5892,5783,5647,5431,5340,6470,6358,6181,6009,5866,5741,5620,5508,5343,5227,6293,6135,5990,5857,5743,5586,5498,5399,5218,5113,6105,5943,5828,5730,5593,5469,5388,5288,5135,5023,5906,5793,5701,5577,5467,5365,5267,5151,5048,4951,5785,5653,5539,5459,5387,5237,5155,5077,4973,4854,7499,7221,6976,6726,6481,6350,6135,5969,5791,5637,7285,6993,6775,6561,6313,6169,5982,5846,5655,5501,7065,6777,6602,6413,6169,6020,5889,5745,5502,5405,6837,6590,6409,6221,6002,5900,5762,5618,5432,5309,6621,6382,6186,6041,5882,5734,5606,5508,5338,5212,6408,6150,5997,5870,5731,5599,5491,5392,5192,5101,6205,5963,5847,5717,5573,5495,5378,5271,5113,5026,6029,5825,5688,5594,5494,5374,5248,5177,5036,4931,5864,5634,5563,5467,5371,5248,5163,5074,4935,4833,5703,5518,5461,5360,5243,5159,5080,4978,4854,4766,7223,6969,6767,6534,6291,6126,5966,5809,5616,5483,6993,6767,6582,6365,6119,5996,5829,5665,5496,5374,6807,6594,6393,6192,6003,5868,5710,5556,5418,5259,6627,6376,6224,6080,5849,5721,5613,5484,5293,5161,6414,6175,6037,5886,5705,5603,5495,5362,5194,5101,6226,5999,5847,5722,5582,5487,5365,5257,5103,4982,6057,5822,5705,5594,5470,5333,5262,5166,4992,4886,5889,5662,5582,5479,5360,5247,5174,5074,4921,4824,5737,5556,5438,5351,5274,5163,5041,4959,4832,4721,5598,5425,5328,5245,5184,5061,4962,4881,4755,4620,6945,6788,6541,6350,6103,5947,5793,5646,5495,5427,6770,6578,6360,6195,5971,5817,5664,5555,5361,5302,6579,6381,6222,6038,5820,5717,5561,5442,5258,5204,6397,6211,6043,5884,5707,5602,5452,5337,5185,5125,6238,6026,5866,5765,5599,5472,5352,5249,5088,5021,6054,5842,5716,5606,5445,5362,5250,5138,4971,4937,5885,5706,5590,5463,5322,5253,5162,5028,4891,4858,5759,5585,5453,5373,5260,5149,5033,4967,4812,4735,5611,5434,5341,5271,5159,5041,4978,4863,4715,4647,5476,5325,5248,5154,5056,4974,4871,4765,4616,4557,6736,6548,6365,6171,5920,5777,5649,5487,5403,5344,6544,6369,6182,6010,5787,5667,5517,5370,5293,5220,6384,6208,6021,5858,5689,5556,5412,5307,5201,5111,6216,6021,5891,5755,5567,5433,5325,5208,5108,5015,6045,5864,5758,5600,5439,5350,5240,5111,5020,4957,5888,5722,5593,5474,5344,5221,5117,5009,4931,4827,5781,5562,5463,5377,5224,5122,5033,4926,4841,4706,5638,5447,5365,5267,5135,5034,4978,4835,4743,4644,5509,5342,5257,5140,5066,4965,4833,4741,4645,4535,5399,5216,5133,5067,4972,4881,4776,4649,4567,4450,6548,6352,6163,6007,5753,5635,5465,5426,5319,5239,6362,6185,5984,5868,5644,5484,5387,5334,5192,5122,6190,6017,5886,5718,5521,5403,5289,5219,5094,5043,6046,5897,5722,5591,5436,5326,5179,5140,5021,4965,5901,5751,5601,5496,5330,5210,5099,5060,4932,4853,5738,5578,5488,5380,5195,5121,5006,4956,4835,4751,5614,5461,5363,5243,5111,5021,4914,4848,4712,4644,5521,5348,5239,5160,5043,4949,4833,4772,4630,4541,5403,5228,5147,5067,4930,4842,4756,4660,4530,4446,5268,5145,5054,4976,4874,4756,4646,4568,4443,4367,6334,6157,6012,5845,5593,5458,5428,5299,5215,5145,6165,6011,5859,5706,5491,5373,5321,5200,5129,5051,6038,5858,5706,5599,5396,5250,5201,5139,5024,4937,5879,5722,5609,5484,5286,5163,5135,5021,4932,4873,5759,5613,5503,5363,5207,5084,5034,4956,4841,4793,5621,5488,5366,5249,5124,4990,4914,4867,4762,4655,5500,5329,5246,5163,5015,4900,4842,4741,4644,4562,5402,5247,5156,5043,4933,4837,4743,4640,4539,4464,5291,5163,5060,4942,4860,4749,4652,4547,4460,4370,5207,5037,4965,4876,4751,4654,4580,4468,4365,4286,6138,5976,5813,5685,5457,5404,5304,5224,5149,5037,5989,5826,5680,5556,5330,5298,5210,5139,5045,4964,5844,5712,5575,5438,5231,5220,5113,5001,4970,4893,5729,5581,5451,5340,5170,5118,5014,4949,4859,4784,5622,5470,5354,5259,5070,5024,4939,4875,4777,4695,5464,5350,5249,5148,4967,4932,4856,4759,4651,4589,5363,5246,5152,5022,4906,4847,4713,4661,4578,4477,5293,5138,5026,4967,4824,4743,4655,4559,4482,4396,5191,5047,4961,4859,4718,4653,4525,4473,4353,4274,5081,4970,4874,4757,4629,4592,4455,4356,4306,4206,5939,5796,5662,5522,5374,5309,5230,5134,5047,4980,5798,5678,5536,5397,5293,5197,5131,5038,4965,4891,5705,5548,5427,5296,5192,5092,5014,4995,4880,4781,5565,5418,5320,5214,5076,5006,4953,4849,4776,4694,5472,5345,5213,5108,5032,4929,4865,4764,4676,4598,5380,5223,5106,5005,4939,4832,4750,4678,4599,4501,5276,5115,5022,4944,4811,4717,4663,4565,4472,4413,5163,5058,4949,4822,4736,4625,4547,4482,4400,4326,5085,4941,4861,4726,4645,4536,4457,4365,4293,4226,5000,4872,4756,4648,4566,4430,4387,4304,4189,4129};
int get(int a)
{
if(a==0)
return 0;
else
return get(a/10)+a%10;
}
int lim[1000000];
void pre()
{
lim[0]=0;
lim[1]=99999;
for(int i=2;i<100004;i++)
{
lim[i]=lim[i-1]+100000;
}
}
int getans(int num)
{
int ans=0;
int i;
for( i=1;;i++)
{
if(num>=lim[i])
ans+=gsum[i];
else
break;
}
for(int j=lim[i-1]+1;j<=num;j++)
{
if(j%get(j)==0)
ans++;
}
return ans;
}
int main()
{
int a,b;
pre();
int cas;
//for(int i=0;i<=5;i++)
//cout<<lim[i]<<endl;
scanf("%d",&cas);
int T=1;
while(cas--)
{
printf("Case %d: ",T++);
scanf("%d%d",&a,&b);
if(b<a)
swap(a,b);
printf("%d\n",getans(b)-getans(a-1));
}
return 0;
}