1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
#include <bits/stdc++.h>

using namespace std;


long long first_digit(long long x){
	if(x >= 10)	return first_digit(x / 10);
	return x;
}

long long min(long long a , long long b){
	if(a > b)	return b;
	return a;
}

long long max(long long a , long long b){
	if(a < b)	return b;
	return a;
}

long long num_of_dig(long long x){
	if(x >= 10)	return 1 + num_of_dig(x / 10);
	return 1;
}

long long power(long long x, long long n){
	if(n == 0)	return 1;
	return x * power(x, n - 1);
}

long long remove_first(long long x){
	long long f = first_digit(x);
	long long d = 1;
	while(f * 10 * d - x <= 0){
		d *= 10;
	}
	return x - f * d;
}

bool is_pot(long long x){
	bool present[10];
	for (long long i = 0; i < 10; ++i)
	{
		present[i] = 0;
	}
	long long x_temp = x;
	while(x_temp > 0){
		present[x_temp % 10] = true;
		x_temp /= 10;
	}
	if(present[0])	return false;
	for (long long i = 1; i < 10; ++i)
	{
		if(present[i]  and x % i != 0){
			return false;
		}
	}
	return true;
}

long long pot(long long l, long long r){
	long long ans = 0;
	for (long long i = l; i <= r; ++i)
	{
		ans += is_pot(i);
	}
	return ans;
}

// DP[pierwsza cyfra][liczba cyfr][ograniczenia cyfrowe][reszta z dzielenia przez 63]
long long DP[10][16][48][63];
// resrtykcja v_2:v_3:v_5:v_7

// czy cyfra spełnia restrykcję
bool restr[10][48];

long long v_p(long long p, long long x){
	if(x % p != 0)	return 0;
	return 1 + v_p(p, x/p);
}

long long lic_eq(long long x){
	long long last_three = x % 1000;
	long long x_div_1000 = x/1000;
	long long ans = 0;
	for (long long i = 1; i <= last_three; ++i)
	{
		//cout << x_div_1000 * 1000 + i << endl;
		ans += is_pot(x_div_1000 * 1000 + i);
	}
	//cout << "ans = " << ans << endl;
	return ans;
}

//long long dig(long long x, long long index){
//	cout << "to do !" << endl;
//}

long long count(long long x, long long restrictions, long long residue, bool first){
	//return 0;
	//cout << "x = " << x << endl;
	long long ans = 0;
	long long digits;
	long long rest_temp = restrictions;
		long long v_2 = rest_temp % 4;
		rest_temp /= 4;
		long long v_3 = rest_temp % 3;
		rest_temp /= 3;
		long long v_5 = rest_temp % 2;
		rest_temp /= 2;
		long long v_7 = rest_temp;
	if(x > 0){
		long long f = first_digit(x) - 1;
		while(f > 0){
			ans += DP[f][num_of_dig(x)][restrictions][residue];
			f--;
		}
		if(first){
			ans += DP[0][num_of_dig(x)][restrictions][residue];
		}
		
		if(num_of_dig(x) - num_of_dig(remove_first(x)) > 1)	return ans;
		//cout << first_digit(x) << endl;
		if(v_p(2, first_digit(x)) > v_2){
			return ans;
		}
		if(v_p(3, first_digit(x)) > v_3){
			return ans;
		}
		if(v_p(5, first_digit(x)) > v_5){
			return ans;
		}
		if(v_p(7, first_digit(x)) > v_7){
			return ans;
		}
		//cout << "a: " << count(remove_first(x), restrictions, ((residue - first_digit(x) * power(10, num_of_dig(x) - 1)) % 63 + 63) % 63) << endl;
		ans += count(remove_first(x), restrictions, ((residue - first_digit(x) * power(10, num_of_dig(x) - 1)) % 63 + 63) % 63, false);
	}
	return ans;
}

long long lic_higher(long long x){
	//bool para[48]
	//cout << "B: " << x << endl;
	long long last_three = x % 1000;
	long long ans = 0;
	for (long long i = 1; i <= 999; ++i)
	{

		// najpierw trzeba zbadać restrykcje narzucane przez ostatnie 3 cyfry
		long long v_2, v_3, v_5, v_7;
		v_2 = v_3 = v_5 = v_7 = 0;
		bool b = false;
		long long d = 1;
		while(d <= 100){
			long long cur_d = (i % (10 * d) - i % d)/ d;
			//if(i == 332)	cout << "cur_d: " << cur_d << endl;
			if(cur_d == 0){
				b = true;
				break;
			}
			v_2 = max(v_2, v_p(2, cur_d));
			v_3 = max(v_3, v_p(3, cur_d));
			v_5 = max(v_5, v_p(5, cur_d));
			v_7 = max(v_7, v_p(7, cur_d));
			d *= 10;
		}
		if(b){
			continue;
		}
		
		//cout << v_2 << " " << v_3 << " " << v_5 << " " << v_7 << endl;
		if(i % power(2, v_2) != 0 or i % power(5, v_5) != 0){
			//cout << i << endl;
			continue;
		}

		long long restrictions = v_p(2, i) + 4 * v_p(3, i) + 12 * v_p(5, i) + 24 * v_p(7, i);
		// 4332
		//cout << "A" << endl;
		// potem dodajemy count dla każdej możliwej reszty
		for (long long r = 0; r < 63; ++r)
		{
			//cout << i << endl;
			long long total_r = 1000 * r + i;
			//cout << r << " " << (v_p(3, total_r) >= v_3) << " " << (v_p(7, total_r) >= v_7) << endl;
			if(v_p(3, total_r) >= v_3 and v_p(7, total_r) >= v_7){
				restrictions = min(v_p(2, total_r), 3) + 4 * min(2, v_p(3, total_r)) + 12 * min(1, v_p(5, total_r)) + 24 * min(1, v_p(7, total_r));
				if(i == 735){
					//cout << "aa" << r << endl;
					//cout << "Aa: " << restrictions << endl;
				}
				//cout << 1000 * r + i << endl;
				//cout << x/1000 << " " << restrictions << " " << r << endl;
				ans += count(x/1000, restrictions, r, true);

				if(count(x/1000, restrictions, r, true) > 0){
					//if(i == 735)	cout << 1000 * r + i << endl;
				//	v.push_back(i);
					//cout << "total_r = " << total_r << endl;
				}
			} 
		}
		
	}
	return ans;
}

long long lic(long long x){
	if(x < 1001){
		return pot(1, x);
	}
	//cout << (x / 1000 ) * 1000 - 1<< endl;
	//cout << lic_higher((x / 1000 - 1) * 1000) << endl;
	return lic_eq(x) + lic_higher(x) + pot(1, 1000);
}

long long pow10[20];
int main(){
	/*while(true){
		long long a;
		cin >> a;
		cout << remove_first(a) << endl;
	}*/
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	long long l, r;
	//cin >> l >> r;

	for(long long restrictions = 0; restrictions < 48; restrictions++){
			long long rest_temp = restrictions;
			long long v_2 = rest_temp % 4;
			rest_temp /= 4;
			long long v_3 = rest_temp % 3;
			rest_temp /= 3;
			long long v_5 = rest_temp % 2;
			rest_temp /= 2;
			long long v_7 = rest_temp;
			//cout << v_2 << " " << v_3 << " " << v_5 << " " << v_7 << endl;
			for (long long i = 1; i < 10; ++i)
			{
				if(v_p(2, i) <= v_2 and v_p(3, i) <= v_3 and v_p(5, i) <= v_5 and v_p(7, i) <= v_7){
					restr[i][restrictions] = true;
					//cout << i << " " << restrictions << endl;
				}
			}
	}

	pow10[0] = 1;
	for (long long i = 1; i < 20; ++i)
	{
		pow10[i] = (pow10[i - 1] * 10) % 63;
		//cout << pow10[i] << endl;
	}

	for(long long restrictions = 0; restrictions < 48; restrictions++){

		long long rest_temp = restrictions;
		long long v_2 = rest_temp % 4;
		rest_temp /= 4;
		long long v_3 = rest_temp % 3;
		rest_temp /= 3;
		long long v_5 = rest_temp % 2;
		rest_temp /= 2;
		long long v_7 = rest_temp;
		for(long long first_digit = 1; first_digit <= 9; first_digit++){
			// Sprawdzamy czy first_digit mieści się w restykcjach

			if(restr[first_digit][restrictions]){
				DP[first_digit][1][restrictions][first_digit] += 1;
				//cout << first_digit << " " << restrictions << " " << first_digit << endl;
			}
		}
	}
	

	for(long long digits = 2; digits <= 15; digits++){
		for(long long restrictions = 0; restrictions < 48; restrictions++){
			long long rest_temp = restrictions;
			long long v_2 = rest_temp % 4;
			rest_temp /= 4;
			long long v_3 = rest_temp % 3;
			rest_temp /= 3;
			long long v_5 = rest_temp % 2;
			rest_temp /= 2;
			long long v_7 = rest_temp;
			for(long long first_digit = 0; first_digit <= 9; first_digit++){
				if(first_digit == 0){
					for(long long second_digit = 0; second_digit < 10; second_digit++){
						for(long long rest = 0; rest < 63; rest++){
							DP[0][digits][restrictions][rest] += DP[second_digit][digits - 1][restrictions][rest];
						}
						//cout << first_digit << " " << digits << " " << restrictions << " " << rest << ": " << DP[first_digit][digits][restrictions][rest] << endl;
					}
				}
				// Sprawdzamy czy first_digit mieści się w restykcjach
				if(!restr[first_digit][restrictions]){
					continue;
				}
				for(long long rest = 0; rest < 63; rest++){
					for(long long second_digit = 1; second_digit < 10; second_digit++){
						DP[first_digit][digits][restrictions][rest] += DP[second_digit][digits - 1][restrictions][((rest - first_digit * pow10[digits - 1]) % 63 + 63) % 63];
						//cout << first_digit << " " << digits << " " << restrictions << " " << rest << ": " << DP[first_digit][digits][restrictions][rest] << endl;
					}
				}
			}
		}
	}

	/*long long f, d, rst, re;
	while(true){
		cin >> f >> d >> rst >> re;
		cout << DP[f][d][rst][re] << endl;
		return 0;
	}*/
	cin >> l >> r ;//>> r;
	/*lic(l);
	sort(v.begin(), v.end());
	v.erase( unique( v.begin(), v.end() ), v.end() );

	sort(v.begin(), v.end());
	for(long long i : v){
		cout << i << endl;
	}*/
	cout << lic(r) - lic(l - 1) << endl;
}