#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const long long INFll = 1000000000000000000ll;
const int MOD = 1000000007;
int n, m, k, l, r;
const int f[100000] = {
    0,    4784, 4194, 4003, 3920, 3831, 3791, 3726, 3667, 3669, 3591, 3642,
    3612, 3532, 3554, 3507, 3500, 3517, 3449, 3496, 3432, 3462, 3406, 3394,
    3376, 3378, 3445, 3362, 3368, 3371, 3305, 3369, 3386, 3336, 3320, 3302,
    3273, 3356, 3286, 3307, 3284, 3327, 3291, 3247, 3251, 3306, 3241, 3278,
    3231, 3271, 3248, 3239, 3184, 3227, 3204, 3235, 3210, 3216, 3191, 3211,
    3222, 3193, 3206, 3234, 3157, 3149, 3191, 3188, 3193, 3225, 3192, 3182,
    3138, 3152, 3135, 3106, 3167, 3211, 3130, 3141, 3137, 3125, 3129, 3135,
    3122, 3125, 3160, 3154, 3168, 3106, 3117, 3076, 3149, 3118, 3135, 3063,
    3171, 3091, 3103, 3099, 3075, 3087, 3126, 3071, 3086, 3114, 3074, 3101,
    3069, 3091, 3080, 3080, 3101, 3067, 3111, 3079, 3117, 3093, 3089, 3103,
    3073, 3040, 3054, 3122, 3079, 3021, 3024, 3098, 3068, 3057, 3013, 3014,
    3077, 3020, 3073, 3038, 3027, 3039, 3044, 3061, 3012, 2998, 3043, 3054,
    3066, 3018, 3025, 3037, 3035, 3015, 3010, 3004, 3014, 3018, 2931, 2994,
    3015, 3025, 3032, 3075, 3031, 2990, 2994, 3030, 2994, 3050, 2997, 2973,
    3008, 3017, 3034, 2998, 2962, 3052, 2980, 2996, 3025, 3000, 2994, 2973,
    3022, 2961, 2981, 3039, 2964, 2968, 2941, 3016, 2992, 3014, 2978, 2983,
    3006, 2970, 2968, 2999, 2936, 2985, 2983, 2950, 3034, 2953, 2964, 2930,
    2950, 2965, 2996, 2968, 2960, 2962, 2952, 2972, 2933, 3012, 2982, 3002,
    2904, 2965, 2963, 2974, 3012, 2915, 2921, 2947, 2908, 2934, 2998, 2925,
    2951, 2971, 2936, 2986, 2949, 2951, 2958, 2936, 2930, 2957, 2895, 2926,
    2934, 2899, 2971, 3011, 2951, 2937, 2925, 2916, 2968, 2931, 2927, 2944,
    2913, 2902, 2936, 2912, 2925, 2955, 2939, 2936, 2912, 2935, 2905, 2928,
    2956, 2968, 2923, 2953, 2902, 2938, 2928, 2928, 2902, 2886, 2942, 2873,
    2980, 2886, 2911, 2920, 2922, 2968, 2876, 2924, 2904, 2952, 2885, 2910,
    2924, 2901, 2928, 2887, 2887, 2961, 2911, 2882, 2896, 2897, 2874, 2941,
    2958, 2898, 2926, 2916, 2933, 2873, 2969, 2886, 2907, 2938, 2845, 2855,
    2898, 2883, 2900, 2902, 2887, 2889, 2877, 2905, 2879, 2901, 2891, 2867,
    2867, 2869, 2906, 2888, 2893, 2870, 2921, 2878, 2910, 2914, 2864, 2879,
    2898, 2841, 2919, 2943, 2856, 2817, 2837, 2899, 2823, 2901, 2878, 2824,
    2888, 2880, 2906, 2855, 2854, 2907, 2902, 2862, 2859, 2918, 2890, 2835,
    2847, 2898, 2844, 2923, 2857, 2884, 2917, 2840, 2875, 2831, 2880, 2907,
    2916, 2859, 2861, 2831, 2841, 2871, 2854, 2898, 2849, 2905, 2896, 2903,
    2868, 2835, 2845, 2853, 2926, 2874, 2849, 2832, 2876, 2859, 2885, 2887,
    2853, 2913, 2828, 2842, 2820, 2900, 2805, 2866, 2860, 2877, 2834, 2852,
    2923, 2817, 2850, 2840, 2884, 2796, 2860, 2885, 2826, 2842, 2842, 2843,
    2799, 2817, 2871, 2909, 2841, 2853, 2791, 2809, 2854, 2815, 2832, 2818,
    2866, 2800, 2872, 2877, 2865, 2774, 2846, 2881, 2890, 2847, 2805, 2869,
    2789, 2850, 2828, 2844, 2850, 2846, 2827, 2821, 2783, 2882, 2855, 2823,
    2845, 2853, 2821, 2840, 2792, 2822, 2788, 2859, 2846, 2819, 2805, 2890,
    2830, 2846, 2881, 2755, 2890, 2829, 2813, 2862, 2820, 2835, 2828, 2871,
    2810, 2840, 2826, 2778, 2865, 2835, 2837, 2809, 2800, 2840, 2826, 2836,
    2807, 2829, 2834, 2822, 2843, 2815, 2806, 2861, 2805, 2786, 2842, 2792,
    2813, 2841, 2840, 2817, 2827, 2795, 2816, 2780, 2799, 2796, 2897, 2789,
    2820, 2738, 2852, 2791, 2818, 2863, 2787, 2765, 2826, 2773, 2820, 2823,
    2817, 2784, 2812, 2770, 2814, 2856, 2793, 2778, 2781, 2822, 2779, 2809,
    2850, 2793, 2835, 2765, 2790, 2760, 2869, 2785, 2801, 2769, 2866, 2861,
    2767, 2812, 2767, 2790, 2765, 2841, 2805, 2816, 2811, 2808, 2894, 2762,
    2769, 2810, 2756, 2848, 2802, 2760, 2762, 2776, 2802, 2837, 2832, 2802,
    2813, 2785, 2757, 2828, 2785, 2791, 2765, 2781, 2835, 2755, 2835, 2779,
    2784, 2802, 2765, 2765, 2800, 2756, 2746, 2808, 2797, 2802, 2800, 2830,
    2795, 2793, 2772, 2783, 2822, 2839, 2768, 2826, 2800, 2797, 2776, 2769,
    2727, 2790, 2774, 2821, 2716, 2761, 2788, 2755, 2812, 2854, 2782, 2796,
    2789, 2746, 2762, 2767, 2807, 2770, 2774, 2784, 2805, 2744, 2805, 2772,
    2761, 2768, 2844, 2807, 2778, 2792, 2812, 2842, 2775, 2773, 2728, 2792,
    2757, 2783, 2777, 2831, 2752, 2829, 2711, 2844, 2745, 2803, 2774, 2780,
    2752, 2791, 2809, 2749, 2806, 2771, 2777, 2801, 2768, 2725, 2786, 2728,
    2779, 2792, 2809, 2820, 2767, 2745, 2771, 2768, 2815, 2729, 2783, 2791,
    2766, 2807, 2753, 2769, 2811, 2743, 2764, 2783, 2807, 2713, 2813, 2769,
    2777, 2820, 2728, 2741, 2748, 2765, 2791, 2760, 2745, 2781, 2788, 2755,
    2741, 2739, 2746, 2767, 2767, 2808, 2735, 2778, 2787, 2766, 2695, 2826,
    2731, 2794, 2743, 2777, 2765, 2769, 2780, 2801, 2754, 2789, 2751, 2768,
    2691, 2752, 2778, 2740, 2795, 2771, 2750, 2779, 2710, 2718, 2741, 2764,
    2799, 2749, 2788, 2741, 2785, 2768, 2735, 2761, 2728, 2759, 2777, 2809,
    2775, 2738, 2771, 2786, 2776, 2731, 2760, 2702, 2774, 2749, 2760, 2765,
    2724, 2747, 2798, 2763, 2766, 2758, 2767, 2749, 2717, 2700, 2758, 2733,
    2747, 2734, 2766, 2764, 2765, 2728, 2757, 2705, 2792, 2683, 2754, 2773,
    2739, 2720, 2747, 2781, 2726, 2769, 2756, 2734, 2698, 2765, 2732, 2771,
    2769, 2752, 2724, 2721, 2765, 2766, 2733, 2806, 2754, 2717, 2729, 2773,
    2737, 2774, 2734, 2757, 2797, 2772, 2680, 2716, 2745, 2736, 2758, 2746,
    2748, 2776, 2777, 2723, 2669, 2760, 2689, 2758, 2748, 2750, 2718, 2809,
    2824, 2664, 2749, 2717, 2774, 2775, 2713, 2685, 2758, 2725, 2767, 2724,
    2710, 2719, 2785, 2782, 2755, 2715, 2762, 2700, 2695, 2778, 2724, 2706,
    2752, 2740, 2747, 2702, 2700, 2739, 2716, 2792, 2717, 2765, 2704, 2700,
    2783, 2750, 2743, 2771, 2747, 2744, 2710, 2765, 2729, 2760, 2638, 2781,
    2735, 2739, 2725, 2708, 2779, 2769, 2706, 2729, 2717, 2718, 2690, 2762,
    2688, 2692, 2720, 2759, 2756, 2727, 2739, 2683, 2736, 2710, 2697, 2731,
    2724, 2806, 2707, 2693, 2649, 2741, 2725, 2700, 2751, 2724, 2765, 2710,
    2749, 2752, 2714, 2760, 2747, 2754, 2670, 2699, 2730, 2717, 2736, 2731,
    2699, 2677, 2697, 2714, 2789, 2778, 2702, 2705, 2677, 2701, 2761, 2749,
    2699, 2781, 2755, 2697, 2699, 2733, 2710, 2769, 2736, 2699, 2701, 2727,
    2757, 2706, 2747, 2669, 2727, 2700, 2722, 2754, 2726, 2714, 2734, 2735,
    2687, 2730, 2669, 2725, 2745, 2688, 2729, 2722, 2737, 2691, 2722, 2728,
    2683, 2699, 2772, 2725, 2659, 2731, 2676, 2769, 2683, 2680, 2721, 2697,
    2737, 2704, 2708, 2709, 2735, 2721, 2714, 2721, 2663, 2718, 2695, 2745,
    2691, 2684, 2749, 2713, 2707, 2723, 2704, 2712, 2669, 2763, 2668, 2701,
    2737, 2719, 2696, 2749, 2769, 2676, 2723, 2729, 2683, 2746, 2688, 2735,
    2624, 2698, 2700, 2729, 2684, 2704, 2676, 2692, 2779, 2710, 2719, 2744,
    2724, 2705, 2699, 2697, 2697, 2727, 2685, 2734, 2674, 2712, 2714, 2699,
    2716, 2680, 2709, 2679, 2696, 2732, 2704, 2712, 2661, 2702, 2735, 2695,
    2663, 2726, 2645, 2758, 2735, 2696, 2755, 2696, 2668, 2744, 2717, 2695,
    2622, 2708, 2712, 2711, 2715, 2747, 2700, 2745, 2701, 2684, 2720, 2688,
    2749, 2726, 2652, 2759, 2665, 2714, 2716, 2700, 2764, 2701, 2644, 2677,
    2656, 2727, 2658, 2743, 2695, 2723, 2693, 2705, 2698, 2657, 2731, 2674,
    2698, 2705, 2761, 2728, 2717, 2743, 2722, 2699, 2698, 2633, 2686, 2703,
    2750, 2680, 2662, 2714, 2716, 2656, 2696, 2685, 2655, 2694, 2652, 2671,
    2653, 2668, 2713, 2685, 2697, 2685, 2642, 2782, 2694, 2664, 2675, 2710,
    2689, 2736, 2651, 2702, 2698, 2673, 2705, 2632, 2732, 2707, 2682, 2684,
    2726, 2622, 2688, 2670, 2657, 2680, 2711, 2694, 2654, 2722, 2697, 2681,
    2730, 2674, 2673, 2666, 2701, 2717, 2717, 2692, 2681, 2698, 2710, 2670,
    2626, 2674, 2696, 2719, 2689, 2699, 2690, 2674, 2727, 2675, 2688, 2687,
    2677, 2688, 2640, 2709, 2627, 2691, 2664, 2714, 2664, 2724, 2675, 2733,
    2680, 2641, 2684, 2706, 2717, 2611, 2696, 2662, 2693, 2712, 2636, 2651,
    2719, 2685, 2673, 2689, 2708, 2729, 2677, 2678, 2735, 2693, 2703, 2661,
    2710, 2680, 2686, 2656, 2732, 2674, 2674, 2713, 2699, 2670, 2640, 2689,
    2709, 2646, 2717, 2646, 2705, 2690, 2677, 2660, 2660, 2664, 2721, 2676,
    2689, 2675, 2697, 2709, 2616, 2671, 2714, 2675, 2653, 2661, 2717, 2742,
    2662, 2656, 2688, 2716, 2658, 2701, 2675, 2681, 2678, 2725, 2649, 2679,
    2656, 2641, 2720, 2708, 2735, 2734, 2665, 2643, 2719, 2659, 2670, 2718,
    2679, 2676, 2742, 2578, 2697, 2638, 2646, 2626, 2720, 2656, 2628, 2697,
    2719, 2666, 2710, 2658, 2678, 2715, 2704, 2688, 2683, 2702, 2658, 2630,
    2700, 2665, 2684, 2711, 2646, 2670, 2707, 2655, 2673, 2690, 2613, 2737,
    2674, 2584, 2703, 2695, 2667, 2643, 2651, 2645, 2710, 2661, 2671, 2699,
    2691, 2720, 2641, 2677, 2670, 2659, 2695, 2709, 2646, 2677, 2631, 2709,
    2585, 2655, 2687, 2638, 2653, 2637, 2667, 2635, 2686, 2732, 2672, 2695,
    2658, 2631, 2658, 2643, 2629, 2693, 2671, 2705, 2686, 2665, 2707, 2629,
    2577, 2650, 2669, 2590, 2681, 2662, 2688, 2649, 2647, 2705, 2684, 2653,
    2705, 2636, 2693, 2726, 2693, 2684, 2680, 2639, 2727, 2724, 2652, 2609,
    2662, 2643, 2669, 2656, 2619, 2598, 2707, 2612, 2648, 2696, 2710, 2609,
    2703, 2671, 2698, 2657, 2664, 2699, 2642, 2671, 2706, 2635, 2615, 2669,
    2659, 2671, 2639, 2707, 2627, 2709, 2687, 2657, 2649, 2654, 2690, 2657,
    2680, 2672, 2671, 2681, 2701, 2645, 2652, 2704, 2605, 2653, 2655, 2684,
    2647, 2678, 2649, 2669, 2639, 2646, 2654, 2694, 2672, 2663, 2667, 2676,
    2652, 2670, 2650, 2653, 2671, 2662, 2678, 2697, 2616, 2647, 2687, 2675,
    2678, 2603, 2630, 2639, 2687, 2683, 2618, 2646, 2652, 2661, 2667, 2639,
    2652, 2670, 2611, 2641, 2669, 2623, 2690, 2642, 2670, 2625, 2704, 2671,
    2628, 2643, 2655, 2632, 2650, 2668, 2629, 2641, 2667, 2615, 2617, 2664,
    2636, 2658, 2655, 2646, 2633, 2628, 2703, 2639, 2693, 2641, 2604, 2596,
    2601, 2666, 2623, 2663, 2670, 2633, 2641, 2687, 2627, 2609, 2669, 2642,
    2706, 2688, 2670, 2701, 2618, 2679, 2643, 2645, 2637, 2628, 2658, 2649,
    2602, 2682, 2654, 2660, 2614, 2679, 2584, 2662, 2711, 2637, 2617, 2640,
    2652, 2730, 2665, 2639, 2663, 2658, 2651, 2670, 2666, 2645, 2655, 2599,
    2608, 2677, 2652, 2698, 2651, 2620, 2617, 2634, 2659, 2678, 2590, 2653,
    2667, 2648, 2535, 2634, 2616, 2632, 2686, 2653, 2650, 2596, 2645, 2672,
    2691, 2602, 2667, 2659, 2648, 2588, 2695, 2645, 2641, 2673, 2653, 2634,
    2603, 2717, 2621, 2725, 2641, 2626, 2588, 2653, 2646, 2635, 2639, 2621,
    2625, 2611, 2657, 2662, 2673, 2648, 2648, 2649, 2663, 2634, 2623, 2645,
    2631, 2678, 2642, 2628, 2692, 2710, 2639, 2667, 2661, 2612, 2611, 2695,
    2629, 2616, 2652, 2671, 2597, 2648, 2621, 2587, 2639, 2644, 2632, 2679,
    2610, 2602, 2632, 2647, 2682, 2559, 2641, 2671, 2658, 2697, 2604, 2614,
    2647, 2604, 2650, 2646, 2646, 2636, 2610, 2706, 2584, 2628, 2629, 2673,
    2640, 2632, 2628, 2644, 2636, 2631, 2626, 2708, 2594, 2651, 2628, 2703,
    2671, 2641, 2672, 2683, 2635, 2597, 2638, 2646, 2583, 2677, 2662, 2624,
    2648, 2644, 2618, 2607, 2583, 2660, 2623, 2671, 2630, 2665, 2643, 2641,
    2621, 2603, 2666, 2628, 2604, 2665, 2652, 2638, 2644, 2624, 2638, 2632,
    2644, 2631, 2622, 2627, 2694, 2621, 2681, 2641, 2660, 2658, 2572, 2626,
    2654, 2635, 2636, 2625, 2640, 2648, 2620, 2558, 2675, 2651, 2618, 2629,
    2651, 2668, 2619, 2646, 2662, 2613, 2605, 2621, 2645, 2628, 2599, 2649,
    2657, 2616, 2613, 2654, 2640, 2605, 2670, 2652, 2635, 2604, 2691, 2610,
    2617, 2614, 2647, 2652, 2668, 2660, 2647, 2621, 2604, 2629, 2623, 2649,
    2630, 2706, 2579, 2672, 2618, 2629, 2657, 2641, 2614, 2652, 2697, 2659,
    2630, 2645, 2610, 2622, 2607, 2623, 2645, 2600, 2634, 2599, 2583, 2645,
    2587, 2671, 2646, 2613, 2604, 2649, 2635, 2599, 2693, 2620, 2667, 2622,
    2545, 2597, 2604, 2640, 2635, 2593, 2605, 2656, 2627, 2587, 2623, 2633,
    2631, 2654, 2618, 2605, 2624, 2623, 2631, 2670, 2639, 2629, 2648, 2645,
    2655, 2615, 2635, 2625, 2669, 2625, 2647, 2603, 2584, 2608, 2612, 2620,
    2658, 2653, 2637, 2584, 2617, 2641, 2602, 2630, 2617, 2668, 2619, 2626,
    2671, 2618, 2635, 2663, 2576, 2557, 2642, 2603, 2650, 2646, 2688, 2567,
    2614, 2627, 2614, 2674, 2616, 2562, 2615, 2640, 2691, 2630, 2635, 2638,
    2614, 2620, 2625, 2621, 2681, 2622, 2607, 2588, 2649, 2553, 2606, 2592,
    2568, 2565, 2591, 2665, 2600, 2595, 2623, 2640, 2596, 2578, 2617, 2571,
    2625, 2611, 2602, 2605, 2640, 2629, 2633, 2666, 2626, 2668, 2613, 2665,
    2619, 2558, 2603, 2629, 2635, 2676, 2599, 2623, 2619, 2632, 2611, 2613,
    2627, 2634, 2583, 2631, 2627, 2640, 2649, 2618, 2640, 2565, 2616, 2620,
    2627, 2623, 2648, 2597, 2629, 2630, 2587, 2588, 2621, 2645, 2620, 2580,
    2596, 2648, 2584, 2606, 2572, 2656, 2548, 2598, 2602, 2584, 2610, 2628,
    2630, 2570, 2623, 2592, 2653, 2630, 2635, 2654, 2635, 2555, 2592, 2598,
    2584, 2638, 2697, 2592, 2614, 2606, 2566, 2610, 2685, 2664, 2686, 2616,
    2547, 2628, 2632, 2562, 2638, 2607, 2588, 2679, 2650, 2604, 2637, 2614,
    2562, 2613, 2620, 2632, 2657, 2626, 2654, 2589, 2640, 2577, 2635, 2566,
    2606, 2645, 2569, 2610, 2630, 2616, 2670, 2630, 2565, 2646, 2601, 2626,
    2629, 2592, 2598, 2551, 2627, 2661, 2621, 2654, 2576, 2643, 2614, 2591,
    2583, 2618, 2596, 2586, 2585, 2590, 2664, 2601, 2587, 2629, 2608, 2635,
    2576, 2620, 2625, 2530, 2660, 2628, 2634, 2562, 2598, 2640, 2621, 2636,
    2628, 2596, 2609, 2543, 2619, 2562, 2625, 2591, 2584, 2619, 2585, 2615,
    2639, 2587, 2592, 2605, 2573, 2563, 2662, 2659, 2607, 2673, 2641, 2578,
    2607, 2596, 2664, 2614, 2625, 2557, 2613, 2617, 2555, 2603, 2594, 2615,
    2681, 2632, 2633, 2644, 2561, 2636, 2581, 2631, 2611, 2595, 2572, 2635,
    2632, 2620, 2615, 2641, 2593, 2590, 2675, 2620, 2589, 2600, 2623, 2609,
    2606, 2624, 2561, 2594, 2631, 2622, 2623, 2577, 2581, 2603, 2574, 2639,
    2616, 2620, 2640, 2642, 2627, 2587, 2637, 2612, 2603, 2621, 2599, 2606,
    2639, 2645, 2617, 2633, 2618, 2596, 2596, 2592, 2600, 2616, 2581, 2590,
    2606, 2598, 2646, 2576, 2545, 2591, 2636, 2556, 2604, 2636, 2635, 2599,
    2575, 2527, 2616, 2607, 2610, 2572, 2589, 2643, 2545, 2650, 2608, 2615,
    2585, 2627, 2536, 2603, 2587, 2612, 2643, 2597, 2654, 2544, 2610, 2605,
    2558, 2618, 2553, 2616, 2604, 2688, 2559, 2577, 2581, 2642, 2619, 2550,
    2609, 2642, 2613, 2616, 2544, 2599, 2675, 2639, 2594, 2547, 2645, 2595,
    2618, 2602, 2551, 2637, 2667, 2596, 2600, 2590, 2515, 2615, 2577, 2635,
    2647, 2605, 2590, 2568, 2592, 2657, 2672, 2627, 2578, 2544, 2563, 2560,
    2609, 2593, 2617, 2660, 2562, 2638, 2567, 2575, 2599, 2599, 2593, 2636,
    2649, 2665, 2569, 2608, 2638, 2585, 2626, 2563, 2547, 2525, 2543, 2581,
    2597, 2595, 2608, 2572, 2570, 2555, 2581, 2648, 2624, 2545, 2632, 2578,
    2625, 2564, 2578, 2629, 2569, 2579, 2576, 2568, 2637, 2630, 2598, 2566,
    2595, 2598, 2625, 2614, 2621, 2578, 2531, 2608, 2580, 2594, 2595, 2611,
    2568, 2640, 2577, 2612, 2635, 2571, 2602, 2606, 2588, 2624, 2567, 2611,
    2638, 2590, 2604, 2549, 2585, 2550, 2576, 2601, 2619, 2600, 2604, 2541,
    2600, 2590, 2599, 2578, 2553, 2573, 2606, 2610, 2599, 2637, 2594, 2587,
    2571, 2644, 2591, 2621, 2633, 2570, 2563, 2578, 2592, 2601, 2644, 2581,
    2595, 2577, 2598, 2586, 2658, 2609, 2596, 2578, 2595, 2587, 2594, 2578,
    2663, 2561, 2584, 2609, 2576, 2622, 2624, 2583, 2614, 2583, 2551, 2651,
    2613, 2579, 2588, 2544, 2591, 2601, 2582, 2641, 2540, 2623, 2542, 2584,
    2560, 2632, 2564, 2631, 2621, 2618, 2631, 2558, 2556, 2615, 2587, 2561,
    2664, 2597, 2603, 2597, 2599, 2524, 2594, 2593, 2606, 2552, 2564, 2520,
    2597, 2599, 2555, 2526, 2599, 2628, 2572, 2602, 2503, 2642, 2538, 2596,
    2598, 2623, 2578, 2635, 2568, 2525, 2635, 2589, 2562, 2594, 2618, 2617,
    2581, 2673, 2595, 2572, 2616, 2616, 2590, 2605, 2597, 2577, 2579, 2587,
    2561, 2512, 2621, 2566, 2574, 2584, 2601, 2571, 2575, 2611, 2579, 2573,
    2604, 2519, 2590, 2620, 2570, 2532, 2579, 2558, 2615, 2538, 2613, 2631,
    2623, 2585, 2571, 2596, 2593, 2602, 2591, 2578, 2604, 2565, 2600, 2518,
    2591, 2576, 2585, 2570, 2596, 2570, 2601, 2597, 2567, 2556, 2561, 2626,
    2613, 2635, 2627, 2563, 2540, 2566, 2585, 2555, 2590, 2597, 2547, 2579,
    2545, 2645, 2584, 2537, 2548, 2599, 2578, 2506, 2602, 2605, 2552, 2587,
    2594, 2621, 2607, 2585, 2665, 2548, 2564, 2577, 2567, 2567, 2600, 2615,
    2574, 2607, 2582, 2636, 2556, 2621, 2605, 2585, 2560, 2534, 2645, 2589,
    2559, 2602, 2592, 2557, 2601, 2583, 2603, 2588, 2559, 2557, 2566, 2583,
    2545, 2610, 2664, 2557, 2633, 2632, 2579, 2561, 2573, 2560, 2531, 2582,
    2625, 2598, 2546, 2595, 2580, 2608, 2603, 2611, 2602, 2612, 2550, 2559,
    2586, 2620, 2578, 2593, 2597, 2548, 2523, 2576, 2549, 2597, 2585, 2576,
    2598, 2607, 2582, 2582, 2600, 2582, 2642, 2580, 2620, 2575, 2572, 2585,
    2590, 2561, 2551, 2569, 2567, 2579, 2628, 2589, 2607, 2670, 2572, 2547,
    2571, 2615, 2593, 2617, 2612, 2560, 2588, 2563, 2533, 2568, 2614, 2581,
    2531, 2573, 2616, 2597, 2598, 2556, 2562, 2583, 2545, 2651, 2578, 2528,
    2611, 2613, 2626, 2587, 2587, 2583, 2607, 2572, 2614, 2555, 2598, 2565,
    2530, 2584, 2514, 2575, 2550, 2613, 2543, 2600, 2559, 2584, 2566, 2555,
    2630, 2571, 2532, 2594, 2576, 2637, 2525, 2525, 2588, 2594, 2644, 2581,
    2547, 2601, 2621, 2561, 2580, 2582, 2606, 2529, 2541, 2537, 2561, 2567,
    2559, 2521, 2590, 2595, 2622, 2597, 2584, 2592, 2540, 2587, 2544, 2535,
    2554, 2568, 2569, 2530, 2610, 2603, 2621, 2591, 2525, 2556, 2564, 2589,
    2597, 2596, 2557, 2548, 2533, 2579, 2538, 2577, 2524, 2554, 2618, 2604,
    2598, 2570, 2577, 2580, 2604, 2582, 2608, 2563, 2589, 2533, 2610, 2622,
    2566, 2523, 2623, 2517, 2561, 2610, 2569, 2542, 2625, 2566, 2561, 2577,
    2596, 2565, 2534, 2620, 2601, 2516, 2568, 2553, 2598, 2562, 2595, 2560,
    2544, 2614, 2525, 2592, 2595, 2599, 2584, 2531, 2591, 2545, 2525, 2575,
    2561, 2529, 2613, 2555, 2559, 2525, 2600, 2555, 2574, 2554, 2571, 2518,
    2596, 2583, 2646, 2518, 2611, 2521, 2589, 2558, 2544, 2589, 2647, 2557,
    2524, 2557, 2520, 2556, 2586, 2625, 2539, 2619, 2554, 2598, 2580, 2569,
    2554, 2478, 2581, 2583, 2580, 2559, 2573, 2543, 2564, 2551, 2585, 2562,
    2568, 2558, 2612, 2543, 2631, 2578, 2565, 2570, 2556, 2554, 2569, 2610,
    2571, 2527, 2584, 2553, 2596, 2603, 2537, 2492, 2529, 2567, 2641, 2560,
    2573, 2555, 2591, 2527, 2580, 2586, 2526, 2556, 2574, 2510, 2574, 2552,
    2555, 2608, 2551, 2643, 2599, 2567, 2564, 2588, 2557, 2556, 2541, 2577,
    2578, 2606, 2524, 2557, 2603, 2543, 2562, 2617, 2547, 2598, 2578, 2532,
    2463, 2549, 2566, 2583, 2589, 2604, 2588, 2545, 2569, 2540, 2573, 2540,
    2637, 2546, 2537, 2577, 2596, 2608, 2601, 2611, 2585, 2546, 2571, 2520,
    2516, 2543, 2603, 2584, 2601, 2557, 2567, 2597, 2577, 2555, 2515, 2547,
    2550, 2524, 2530, 2600, 2570, 2615, 2543, 2556, 2552, 2583, 2552, 2564,
    2557, 2570, 2599, 2573, 2547, 2605, 2551, 2559, 2594, 2544, 2595, 2533,
    2541, 2538, 2574, 2568, 2585, 2553, 2570, 2539, 2551, 2570, 2516, 2531,
    2553, 2575, 2600, 2642, 2566, 2516, 2547, 2562, 2541, 2616, 2557, 2544,
    2528, 2567, 2564, 2525, 2635, 2538, 2576, 2541, 2591, 2596, 2582, 2476,
    2567, 2543, 2511, 2537, 2530, 2511, 2570, 2599, 2531, 2544, 2620, 2530,
    2558};
inline bool prime(int x) {
  if (x < 2) return 0;
  int j = 2;
  while (j * j <= x) {
    if (x % j == 0) {
      return 0;
    }
    if (j == 2)
      j++;
    else
      j += 2;
  }
  return 1;
}
inline int ans(int x) {
  int j = x / 100000;
  int ret = 0;
  if (x >= 2) ret++;
  for (int i = 0; i <= j; ++i) {
    ret += f[i];
  }
  if (j > 0) ret--;
  int b = j * 100000;
  b++;
  for (int i = b; i <= x; i += 4) {
    if (prime(i)) ret++;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> l >> r;
  cout << ans(r) - ans(l - 1) << endl;
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

On the math lesson a teacher asked each pupil to come up with his own lucky numbers. As a fan of number theory Peter chose prime numbers. Bob was more original. He said that number t is his lucky number, if it can be represented as: 

t = a2 + b2,  where a, b are arbitrary positive integers.

Now, the boys decided to find out how many days of the interval [l, r] (l ≤ r) are suitable for pair programming. They decided that the day i (l ≤ i ≤ r) is suitable for pair programming if and only if the number i is lucky for Peter and lucky for Bob at the same time. Help the boys to find the number of such days.

Input

The first line of the input contains integer numbers l, r (1 ≤ l, r ≤ 3·108).

Output

In the only line print the number of days on the segment [l, r], which are lucky for Peter and Bob at the same time.

Examples

Input

3 5


Output

1


Input

6 66


Output

7

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const long long INFll = 1000000000000000000ll;
const int MOD = 1000000007;
int n, m, k, l, r;
const int f[100000] = {
    0,    4784, 4194, 4003, 3920, 3831, 3791, 3726, 3667, 3669, 3591, 3642,
    3612, 3532, 3554, 3507, 3500, 3517, 3449, 3496, 3432, 3462, 3406, 3394,
    3376, 3378, 3445, 3362, 3368, 3371, 3305, 3369, 3386, 3336, 3320, 3302,
    3273, 3356, 3286, 3307, 3284, 3327, 3291, 3247, 3251, 3306, 3241, 3278,
    3231, 3271, 3248, 3239, 3184, 3227, 3204, 3235, 3210, 3216, 3191, 3211,
    3222, 3193, 3206, 3234, 3157, 3149, 3191, 3188, 3193, 3225, 3192, 3182,
    3138, 3152, 3135, 3106, 3167, 3211, 3130, 3141, 3137, 3125, 3129, 3135,
    3122, 3125, 3160, 3154, 3168, 3106, 3117, 3076, 3149, 3118, 3135, 3063,
    3171, 3091, 3103, 3099, 3075, 3087, 3126, 3071, 3086, 3114, 3074, 3101,
    3069, 3091, 3080, 3080, 3101, 3067, 3111, 3079, 3117, 3093, 3089, 3103,
    3073, 3040, 3054, 3122, 3079, 3021, 3024, 3098, 3068, 3057, 3013, 3014,
    3077, 3020, 3073, 3038, 3027, 3039, 3044, 3061, 3012, 2998, 3043, 3054,
    3066, 3018, 3025, 3037, 3035, 3015, 3010, 3004, 3014, 3018, 2931, 2994,
    3015, 3025, 3032, 3075, 3031, 2990, 2994, 3030, 2994, 3050, 2997, 2973,
    3008, 3017, 3034, 2998, 2962, 3052, 2980, 2996, 3025, 3000, 2994, 2973,
    3022, 2961, 2981, 3039, 2964, 2968, 2941, 3016, 2992, 3014, 2978, 2983,
    3006, 2970, 2968, 2999, 2936, 2985, 2983, 2950, 3034, 2953, 2964, 2930,
    2950, 2965, 2996, 2968, 2960, 2962, 2952, 2972, 2933, 3012, 2982, 3002,
    2904, 2965, 2963, 2974, 3012, 2915, 2921, 2947, 2908, 2934, 2998, 2925,
    2951, 2971, 2936, 2986, 2949, 2951, 2958, 2936, 2930, 2957, 2895, 2926,
    2934, 2899, 2971, 3011, 2951, 2937, 2925, 2916, 2968, 2931, 2927, 2944,
    2913, 2902, 2936, 2912, 2925, 2955, 2939, 2936, 2912, 2935, 2905, 2928,
    2956, 2968, 2923, 2953, 2902, 2938, 2928, 2928, 2902, 2886, 2942, 2873,
    2980, 2886, 2911, 2920, 2922, 2968, 2876, 2924, 2904, 2952, 2885, 2910,
    2924, 2901, 2928, 2887, 2887, 2961, 2911, 2882, 2896, 2897, 2874, 2941,
    2958, 2898, 2926, 2916, 2933, 2873, 2969, 2886, 2907, 2938, 2845, 2855,
    2898, 2883, 2900, 2902, 2887, 2889, 2877, 2905, 2879, 2901, 2891, 2867,
    2867, 2869, 2906, 2888, 2893, 2870, 2921, 2878, 2910, 2914, 2864, 2879,
    2898, 2841, 2919, 2943, 2856, 2817, 2837, 2899, 2823, 2901, 2878, 2824,
    2888, 2880, 2906, 2855, 2854, 2907, 2902, 2862, 2859, 2918, 2890, 2835,
    2847, 2898, 2844, 2923, 2857, 2884, 2917, 2840, 2875, 2831, 2880, 2907,
    2916, 2859, 2861, 2831, 2841, 2871, 2854, 2898, 2849, 2905, 2896, 2903,
    2868, 2835, 2845, 2853, 2926, 2874, 2849, 2832, 2876, 2859, 2885, 2887,
    2853, 2913, 2828, 2842, 2820, 2900, 2805, 2866, 2860, 2877, 2834, 2852,
    2923, 2817, 2850, 2840, 2884, 2796, 2860, 2885, 2826, 2842, 2842, 2843,
    2799, 2817, 2871, 2909, 2841, 2853, 2791, 2809, 2854, 2815, 2832, 2818,
    2866, 2800, 2872, 2877, 2865, 2774, 2846, 2881, 2890, 2847, 2805, 2869,
    2789, 2850, 2828, 2844, 2850, 2846, 2827, 2821, 2783, 2882, 2855, 2823,
    2845, 2853, 2821, 2840, 2792, 2822, 2788, 2859, 2846, 2819, 2805, 2890,
    2830, 2846, 2881, 2755, 2890, 2829, 2813, 2862, 2820, 2835, 2828, 2871,
    2810, 2840, 2826, 2778, 2865, 2835, 2837, 2809, 2800, 2840, 2826, 2836,
    2807, 2829, 2834, 2822, 2843, 2815, 2806, 2861, 2805, 2786, 2842, 2792,
    2813, 2841, 2840, 2817, 2827, 2795, 2816, 2780, 2799, 2796, 2897, 2789,
    2820, 2738, 2852, 2791, 2818, 2863, 2787, 2765, 2826, 2773, 2820, 2823,
    2817, 2784, 2812, 2770, 2814, 2856, 2793, 2778, 2781, 2822, 2779, 2809,
    2850, 2793, 2835, 2765, 2790, 2760, 2869, 2785, 2801, 2769, 2866, 2861,
    2767, 2812, 2767, 2790, 2765, 2841, 2805, 2816, 2811, 2808, 2894, 2762,
    2769, 2810, 2756, 2848, 2802, 2760, 2762, 2776, 2802, 2837, 2832, 2802,
    2813, 2785, 2757, 2828, 2785, 2791, 2765, 2781, 2835, 2755, 2835, 2779,
    2784, 2802, 2765, 2765, 2800, 2756, 2746, 2808, 2797, 2802, 2800, 2830,
    2795, 2793, 2772, 2783, 2822, 2839, 2768, 2826, 2800, 2797, 2776, 2769,
    2727, 2790, 2774, 2821, 2716, 2761, 2788, 2755, 2812, 2854, 2782, 2796,
    2789, 2746, 2762, 2767, 2807, 2770, 2774, 2784, 2805, 2744, 2805, 2772,
    2761, 2768, 2844, 2807, 2778, 2792, 2812, 2842, 2775, 2773, 2728, 2792,
    2757, 2783, 2777, 2831, 2752, 2829, 2711, 2844, 2745, 2803, 2774, 2780,
    2752, 2791, 2809, 2749, 2806, 2771, 2777, 2801, 2768, 2725, 2786, 2728,
    2779, 2792, 2809, 2820, 2767, 2745, 2771, 2768, 2815, 2729, 2783, 2791,
    2766, 2807, 2753, 2769, 2811, 2743, 2764, 2783, 2807, 2713, 2813, 2769,
    2777, 2820, 2728, 2741, 2748, 2765, 2791, 2760, 2745, 2781, 2788, 2755,
    2741, 2739, 2746, 2767, 2767, 2808, 2735, 2778, 2787, 2766, 2695, 2826,
    2731, 2794, 2743, 2777, 2765, 2769, 2780, 2801, 2754, 2789, 2751, 2768,
    2691, 2752, 2778, 2740, 2795, 2771, 2750, 2779, 2710, 2718, 2741, 2764,
    2799, 2749, 2788, 2741, 2785, 2768, 2735, 2761, 2728, 2759, 2777, 2809,
    2775, 2738, 2771, 2786, 2776, 2731, 2760, 2702, 2774, 2749, 2760, 2765,
    2724, 2747, 2798, 2763, 2766, 2758, 2767, 2749, 2717, 2700, 2758, 2733,
    2747, 2734, 2766, 2764, 2765, 2728, 2757, 2705, 2792, 2683, 2754, 2773,
    2739, 2720, 2747, 2781, 2726, 2769, 2756, 2734, 2698, 2765, 2732, 2771,
    2769, 2752, 2724, 2721, 2765, 2766, 2733, 2806, 2754, 2717, 2729, 2773,
    2737, 2774, 2734, 2757, 2797, 2772, 2680, 2716, 2745, 2736, 2758, 2746,
    2748, 2776, 2777, 2723, 2669, 2760, 2689, 2758, 2748, 2750, 2718, 2809,
    2824, 2664, 2749, 2717, 2774, 2775, 2713, 2685, 2758, 2725, 2767, 2724,
    2710, 2719, 2785, 2782, 2755, 2715, 2762, 2700, 2695, 2778, 2724, 2706,
    2752, 2740, 2747, 2702, 2700, 2739, 2716, 2792, 2717, 2765, 2704, 2700,
    2783, 2750, 2743, 2771, 2747, 2744, 2710, 2765, 2729, 2760, 2638, 2781,
    2735, 2739, 2725, 2708, 2779, 2769, 2706, 2729, 2717, 2718, 2690, 2762,
    2688, 2692, 2720, 2759, 2756, 2727, 2739, 2683, 2736, 2710, 2697, 2731,
    2724, 2806, 2707, 2693, 2649, 2741, 2725, 2700, 2751, 2724, 2765, 2710,
    2749, 2752, 2714, 2760, 2747, 2754, 2670, 2699, 2730, 2717, 2736, 2731,
    2699, 2677, 2697, 2714, 2789, 2778, 2702, 2705, 2677, 2701, 2761, 2749,
    2699, 2781, 2755, 2697, 2699, 2733, 2710, 2769, 2736, 2699, 2701, 2727,
    2757, 2706, 2747, 2669, 2727, 2700, 2722, 2754, 2726, 2714, 2734, 2735,
    2687, 2730, 2669, 2725, 2745, 2688, 2729, 2722, 2737, 2691, 2722, 2728,
    2683, 2699, 2772, 2725, 2659, 2731, 2676, 2769, 2683, 2680, 2721, 2697,
    2737, 2704, 2708, 2709, 2735, 2721, 2714, 2721, 2663, 2718, 2695, 2745,
    2691, 2684, 2749, 2713, 2707, 2723, 2704, 2712, 2669, 2763, 2668, 2701,
    2737, 2719, 2696, 2749, 2769, 2676, 2723, 2729, 2683, 2746, 2688, 2735,
    2624, 2698, 2700, 2729, 2684, 2704, 2676, 2692, 2779, 2710, 2719, 2744,
    2724, 2705, 2699, 2697, 2697, 2727, 2685, 2734, 2674, 2712, 2714, 2699,
    2716, 2680, 2709, 2679, 2696, 2732, 2704, 2712, 2661, 2702, 2735, 2695,
    2663, 2726, 2645, 2758, 2735, 2696, 2755, 2696, 2668, 2744, 2717, 2695,
    2622, 2708, 2712, 2711, 2715, 2747, 2700, 2745, 2701, 2684, 2720, 2688,
    2749, 2726, 2652, 2759, 2665, 2714, 2716, 2700, 2764, 2701, 2644, 2677,
    2656, 2727, 2658, 2743, 2695, 2723, 2693, 2705, 2698, 2657, 2731, 2674,
    2698, 2705, 2761, 2728, 2717, 2743, 2722, 2699, 2698, 2633, 2686, 2703,
    2750, 2680, 2662, 2714, 2716, 2656, 2696, 2685, 2655, 2694, 2652, 2671,
    2653, 2668, 2713, 2685, 2697, 2685, 2642, 2782, 2694, 2664, 2675, 2710,
    2689, 2736, 2651, 2702, 2698, 2673, 2705, 2632, 2732, 2707, 2682, 2684,
    2726, 2622, 2688, 2670, 2657, 2680, 2711, 2694, 2654, 2722, 2697, 2681,
    2730, 2674, 2673, 2666, 2701, 2717, 2717, 2692, 2681, 2698, 2710, 2670,
    2626, 2674, 2696, 2719, 2689, 2699, 2690, 2674, 2727, 2675, 2688, 2687,
    2677, 2688, 2640, 2709, 2627, 2691, 2664, 2714, 2664, 2724, 2675, 2733,
    2680, 2641, 2684, 2706, 2717, 2611, 2696, 2662, 2693, 2712, 2636, 2651,
    2719, 2685, 2673, 2689, 2708, 2729, 2677, 2678, 2735, 2693, 2703, 2661,
    2710, 2680, 2686, 2656, 2732, 2674, 2674, 2713, 2699, 2670, 2640, 2689,
    2709, 2646, 2717, 2646, 2705, 2690, 2677, 2660, 2660, 2664, 2721, 2676,
    2689, 2675, 2697, 2709, 2616, 2671, 2714, 2675, 2653, 2661, 2717, 2742,
    2662, 2656, 2688, 2716, 2658, 2701, 2675, 2681, 2678, 2725, 2649, 2679,
    2656, 2641, 2720, 2708, 2735, 2734, 2665, 2643, 2719, 2659, 2670, 2718,
    2679, 2676, 2742, 2578, 2697, 2638, 2646, 2626, 2720, 2656, 2628, 2697,
    2719, 2666, 2710, 2658, 2678, 2715, 2704, 2688, 2683, 2702, 2658, 2630,
    2700, 2665, 2684, 2711, 2646, 2670, 2707, 2655, 2673, 2690, 2613, 2737,
    2674, 2584, 2703, 2695, 2667, 2643, 2651, 2645, 2710, 2661, 2671, 2699,
    2691, 2720, 2641, 2677, 2670, 2659, 2695, 2709, 2646, 2677, 2631, 2709,
    2585, 2655, 2687, 2638, 2653, 2637, 2667, 2635, 2686, 2732, 2672, 2695,
    2658, 2631, 2658, 2643, 2629, 2693, 2671, 2705, 2686, 2665, 2707, 2629,
    2577, 2650, 2669, 2590, 2681, 2662, 2688, 2649, 2647, 2705, 2684, 2653,
    2705, 2636, 2693, 2726, 2693, 2684, 2680, 2639, 2727, 2724, 2652, 2609,
    2662, 2643, 2669, 2656, 2619, 2598, 2707, 2612, 2648, 2696, 2710, 2609,
    2703, 2671, 2698, 2657, 2664, 2699, 2642, 2671, 2706, 2635, 2615, 2669,
    2659, 2671, 2639, 2707, 2627, 2709, 2687, 2657, 2649, 2654, 2690, 2657,
    2680, 2672, 2671, 2681, 2701, 2645, 2652, 2704, 2605, 2653, 2655, 2684,
    2647, 2678, 2649, 2669, 2639, 2646, 2654, 2694, 2672, 2663, 2667, 2676,
    2652, 2670, 2650, 2653, 2671, 2662, 2678, 2697, 2616, 2647, 2687, 2675,
    2678, 2603, 2630, 2639, 2687, 2683, 2618, 2646, 2652, 2661, 2667, 2639,
    2652, 2670, 2611, 2641, 2669, 2623, 2690, 2642, 2670, 2625, 2704, 2671,
    2628, 2643, 2655, 2632, 2650, 2668, 2629, 2641, 2667, 2615, 2617, 2664,
    2636, 2658, 2655, 2646, 2633, 2628, 2703, 2639, 2693, 2641, 2604, 2596,
    2601, 2666, 2623, 2663, 2670, 2633, 2641, 2687, 2627, 2609, 2669, 2642,
    2706, 2688, 2670, 2701, 2618, 2679, 2643, 2645, 2637, 2628, 2658, 2649,
    2602, 2682, 2654, 2660, 2614, 2679, 2584, 2662, 2711, 2637, 2617, 2640,
    2652, 2730, 2665, 2639, 2663, 2658, 2651, 2670, 2666, 2645, 2655, 2599,
    2608, 2677, 2652, 2698, 2651, 2620, 2617, 2634, 2659, 2678, 2590, 2653,
    2667, 2648, 2535, 2634, 2616, 2632, 2686, 2653, 2650, 2596, 2645, 2672,
    2691, 2602, 2667, 2659, 2648, 2588, 2695, 2645, 2641, 2673, 2653, 2634,
    2603, 2717, 2621, 2725, 2641, 2626, 2588, 2653, 2646, 2635, 2639, 2621,
    2625, 2611, 2657, 2662, 2673, 2648, 2648, 2649, 2663, 2634, 2623, 2645,
    2631, 2678, 2642, 2628, 2692, 2710, 2639, 2667, 2661, 2612, 2611, 2695,
    2629, 2616, 2652, 2671, 2597, 2648, 2621, 2587, 2639, 2644, 2632, 2679,
    2610, 2602, 2632, 2647, 2682, 2559, 2641, 2671, 2658, 2697, 2604, 2614,
    2647, 2604, 2650, 2646, 2646, 2636, 2610, 2706, 2584, 2628, 2629, 2673,
    2640, 2632, 2628, 2644, 2636, 2631, 2626, 2708, 2594, 2651, 2628, 2703,
    2671, 2641, 2672, 2683, 2635, 2597, 2638, 2646, 2583, 2677, 2662, 2624,
    2648, 2644, 2618, 2607, 2583, 2660, 2623, 2671, 2630, 2665, 2643, 2641,
    2621, 2603, 2666, 2628, 2604, 2665, 2652, 2638, 2644, 2624, 2638, 2632,
    2644, 2631, 2622, 2627, 2694, 2621, 2681, 2641, 2660, 2658, 2572, 2626,
    2654, 2635, 2636, 2625, 2640, 2648, 2620, 2558, 2675, 2651, 2618, 2629,
    2651, 2668, 2619, 2646, 2662, 2613, 2605, 2621, 2645, 2628, 2599, 2649,
    2657, 2616, 2613, 2654, 2640, 2605, 2670, 2652, 2635, 2604, 2691, 2610,
    2617, 2614, 2647, 2652, 2668, 2660, 2647, 2621, 2604, 2629, 2623, 2649,
    2630, 2706, 2579, 2672, 2618, 2629, 2657, 2641, 2614, 2652, 2697, 2659,
    2630, 2645, 2610, 2622, 2607, 2623, 2645, 2600, 2634, 2599, 2583, 2645,
    2587, 2671, 2646, 2613, 2604, 2649, 2635, 2599, 2693, 2620, 2667, 2622,
    2545, 2597, 2604, 2640, 2635, 2593, 2605, 2656, 2627, 2587, 2623, 2633,
    2631, 2654, 2618, 2605, 2624, 2623, 2631, 2670, 2639, 2629, 2648, 2645,
    2655, 2615, 2635, 2625, 2669, 2625, 2647, 2603, 2584, 2608, 2612, 2620,
    2658, 2653, 2637, 2584, 2617, 2641, 2602, 2630, 2617, 2668, 2619, 2626,
    2671, 2618, 2635, 2663, 2576, 2557, 2642, 2603, 2650, 2646, 2688, 2567,
    2614, 2627, 2614, 2674, 2616, 2562, 2615, 2640, 2691, 2630, 2635, 2638,
    2614, 2620, 2625, 2621, 2681, 2622, 2607, 2588, 2649, 2553, 2606, 2592,
    2568, 2565, 2591, 2665, 2600, 2595, 2623, 2640, 2596, 2578, 2617, 2571,
    2625, 2611, 2602, 2605, 2640, 2629, 2633, 2666, 2626, 2668, 2613, 2665,
    2619, 2558, 2603, 2629, 2635, 2676, 2599, 2623, 2619, 2632, 2611, 2613,
    2627, 2634, 2583, 2631, 2627, 2640, 2649, 2618, 2640, 2565, 2616, 2620,
    2627, 2623, 2648, 2597, 2629, 2630, 2587, 2588, 2621, 2645, 2620, 2580,
    2596, 2648, 2584, 2606, 2572, 2656, 2548, 2598, 2602, 2584, 2610, 2628,
    2630, 2570, 2623, 2592, 2653, 2630, 2635, 2654, 2635, 2555, 2592, 2598,
    2584, 2638, 2697, 2592, 2614, 2606, 2566, 2610, 2685, 2664, 2686, 2616,
    2547, 2628, 2632, 2562, 2638, 2607, 2588, 2679, 2650, 2604, 2637, 2614,
    2562, 2613, 2620, 2632, 2657, 2626, 2654, 2589, 2640, 2577, 2635, 2566,
    2606, 2645, 2569, 2610, 2630, 2616, 2670, 2630, 2565, 2646, 2601, 2626,
    2629, 2592, 2598, 2551, 2627, 2661, 2621, 2654, 2576, 2643, 2614, 2591,
    2583, 2618, 2596, 2586, 2585, 2590, 2664, 2601, 2587, 2629, 2608, 2635,
    2576, 2620, 2625, 2530, 2660, 2628, 2634, 2562, 2598, 2640, 2621, 2636,
    2628, 2596, 2609, 2543, 2619, 2562, 2625, 2591, 2584, 2619, 2585, 2615,
    2639, 2587, 2592, 2605, 2573, 2563, 2662, 2659, 2607, 2673, 2641, 2578,
    2607, 2596, 2664, 2614, 2625, 2557, 2613, 2617, 2555, 2603, 2594, 2615,
    2681, 2632, 2633, 2644, 2561, 2636, 2581, 2631, 2611, 2595, 2572, 2635,
    2632, 2620, 2615, 2641, 2593, 2590, 2675, 2620, 2589, 2600, 2623, 2609,
    2606, 2624, 2561, 2594, 2631, 2622, 2623, 2577, 2581, 2603, 2574, 2639,
    2616, 2620, 2640, 2642, 2627, 2587, 2637, 2612, 2603, 2621, 2599, 2606,
    2639, 2645, 2617, 2633, 2618, 2596, 2596, 2592, 2600, 2616, 2581, 2590,
    2606, 2598, 2646, 2576, 2545, 2591, 2636, 2556, 2604, 2636, 2635, 2599,
    2575, 2527, 2616, 2607, 2610, 2572, 2589, 2643, 2545, 2650, 2608, 2615,
    2585, 2627, 2536, 2603, 2587, 2612, 2643, 2597, 2654, 2544, 2610, 2605,
    2558, 2618, 2553, 2616, 2604, 2688, 2559, 2577, 2581, 2642, 2619, 2550,
    2609, 2642, 2613, 2616, 2544, 2599, 2675, 2639, 2594, 2547, 2645, 2595,
    2618, 2602, 2551, 2637, 2667, 2596, 2600, 2590, 2515, 2615, 2577, 2635,
    2647, 2605, 2590, 2568, 2592, 2657, 2672, 2627, 2578, 2544, 2563, 2560,
    2609, 2593, 2617, 2660, 2562, 2638, 2567, 2575, 2599, 2599, 2593, 2636,
    2649, 2665, 2569, 2608, 2638, 2585, 2626, 2563, 2547, 2525, 2543, 2581,
    2597, 2595, 2608, 2572, 2570, 2555, 2581, 2648, 2624, 2545, 2632, 2578,
    2625, 2564, 2578, 2629, 2569, 2579, 2576, 2568, 2637, 2630, 2598, 2566,
    2595, 2598, 2625, 2614, 2621, 2578, 2531, 2608, 2580, 2594, 2595, 2611,
    2568, 2640, 2577, 2612, 2635, 2571, 2602, 2606, 2588, 2624, 2567, 2611,
    2638, 2590, 2604, 2549, 2585, 2550, 2576, 2601, 2619, 2600, 2604, 2541,
    2600, 2590, 2599, 2578, 2553, 2573, 2606, 2610, 2599, 2637, 2594, 2587,
    2571, 2644, 2591, 2621, 2633, 2570, 2563, 2578, 2592, 2601, 2644, 2581,
    2595, 2577, 2598, 2586, 2658, 2609, 2596, 2578, 2595, 2587, 2594, 2578,
    2663, 2561, 2584, 2609, 2576, 2622, 2624, 2583, 2614, 2583, 2551, 2651,
    2613, 2579, 2588, 2544, 2591, 2601, 2582, 2641, 2540, 2623, 2542, 2584,
    2560, 2632, 2564, 2631, 2621, 2618, 2631, 2558, 2556, 2615, 2587, 2561,
    2664, 2597, 2603, 2597, 2599, 2524, 2594, 2593, 2606, 2552, 2564, 2520,
    2597, 2599, 2555, 2526, 2599, 2628, 2572, 2602, 2503, 2642, 2538, 2596,
    2598, 2623, 2578, 2635, 2568, 2525, 2635, 2589, 2562, 2594, 2618, 2617,
    2581, 2673, 2595, 2572, 2616, 2616, 2590, 2605, 2597, 2577, 2579, 2587,
    2561, 2512, 2621, 2566, 2574, 2584, 2601, 2571, 2575, 2611, 2579, 2573,
    2604, 2519, 2590, 2620, 2570, 2532, 2579, 2558, 2615, 2538, 2613, 2631,
    2623, 2585, 2571, 2596, 2593, 2602, 2591, 2578, 2604, 2565, 2600, 2518,
    2591, 2576, 2585, 2570, 2596, 2570, 2601, 2597, 2567, 2556, 2561, 2626,
    2613, 2635, 2627, 2563, 2540, 2566, 2585, 2555, 2590, 2597, 2547, 2579,
    2545, 2645, 2584, 2537, 2548, 2599, 2578, 2506, 2602, 2605, 2552, 2587,
    2594, 2621, 2607, 2585, 2665, 2548, 2564, 2577, 2567, 2567, 2600, 2615,
    2574, 2607, 2582, 2636, 2556, 2621, 2605, 2585, 2560, 2534, 2645, 2589,
    2559, 2602, 2592, 2557, 2601, 2583, 2603, 2588, 2559, 2557, 2566, 2583,
    2545, 2610, 2664, 2557, 2633, 2632, 2579, 2561, 2573, 2560, 2531, 2582,
    2625, 2598, 2546, 2595, 2580, 2608, 2603, 2611, 2602, 2612, 2550, 2559,
    2586, 2620, 2578, 2593, 2597, 2548, 2523, 2576, 2549, 2597, 2585, 2576,
    2598, 2607, 2582, 2582, 2600, 2582, 2642, 2580, 2620, 2575, 2572, 2585,
    2590, 2561, 2551, 2569, 2567, 2579, 2628, 2589, 2607, 2670, 2572, 2547,
    2571, 2615, 2593, 2617, 2612, 2560, 2588, 2563, 2533, 2568, 2614, 2581,
    2531, 2573, 2616, 2597, 2598, 2556, 2562, 2583, 2545, 2651, 2578, 2528,
    2611, 2613, 2626, 2587, 2587, 2583, 2607, 2572, 2614, 2555, 2598, 2565,
    2530, 2584, 2514, 2575, 2550, 2613, 2543, 2600, 2559, 2584, 2566, 2555,
    2630, 2571, 2532, 2594, 2576, 2637, 2525, 2525, 2588, 2594, 2644, 2581,
    2547, 2601, 2621, 2561, 2580, 2582, 2606, 2529, 2541, 2537, 2561, 2567,
    2559, 2521, 2590, 2595, 2622, 2597, 2584, 2592, 2540, 2587, 2544, 2535,
    2554, 2568, 2569, 2530, 2610, 2603, 2621, 2591, 2525, 2556, 2564, 2589,
    2597, 2596, 2557, 2548, 2533, 2579, 2538, 2577, 2524, 2554, 2618, 2604,
    2598, 2570, 2577, 2580, 2604, 2582, 2608, 2563, 2589, 2533, 2610, 2622,
    2566, 2523, 2623, 2517, 2561, 2610, 2569, 2542, 2625, 2566, 2561, 2577,
    2596, 2565, 2534, 2620, 2601, 2516, 2568, 2553, 2598, 2562, 2595, 2560,
    2544, 2614, 2525, 2592, 2595, 2599, 2584, 2531, 2591, 2545, 2525, 2575,
    2561, 2529, 2613, 2555, 2559, 2525, 2600, 2555, 2574, 2554, 2571, 2518,
    2596, 2583, 2646, 2518, 2611, 2521, 2589, 2558, 2544, 2589, 2647, 2557,
    2524, 2557, 2520, 2556, 2586, 2625, 2539, 2619, 2554, 2598, 2580, 2569,
    2554, 2478, 2581, 2583, 2580, 2559, 2573, 2543, 2564, 2551, 2585, 2562,
    2568, 2558, 2612, 2543, 2631, 2578, 2565, 2570, 2556, 2554, 2569, 2610,
    2571, 2527, 2584, 2553, 2596, 2603, 2537, 2492, 2529, 2567, 2641, 2560,
    2573, 2555, 2591, 2527, 2580, 2586, 2526, 2556, 2574, 2510, 2574, 2552,
    2555, 2608, 2551, 2643, 2599, 2567, 2564, 2588, 2557, 2556, 2541, 2577,
    2578, 2606, 2524, 2557, 2603, 2543, 2562, 2617, 2547, 2598, 2578, 2532,
    2463, 2549, 2566, 2583, 2589, 2604, 2588, 2545, 2569, 2540, 2573, 2540,
    2637, 2546, 2537, 2577, 2596, 2608, 2601, 2611, 2585, 2546, 2571, 2520,
    2516, 2543, 2603, 2584, 2601, 2557, 2567, 2597, 2577, 2555, 2515, 2547,
    2550, 2524, 2530, 2600, 2570, 2615, 2543, 2556, 2552, 2583, 2552, 2564,
    2557, 2570, 2599, 2573, 2547, 2605, 2551, 2559, 2594, 2544, 2595, 2533,
    2541, 2538, 2574, 2568, 2585, 2553, 2570, 2539, 2551, 2570, 2516, 2531,
    2553, 2575, 2600, 2642, 2566, 2516, 2547, 2562, 2541, 2616, 2557, 2544,
    2528, 2567, 2564, 2525, 2635, 2538, 2576, 2541, 2591, 2596, 2582, 2476,
    2567, 2543, 2511, 2537, 2530, 2511, 2570, 2599, 2531, 2544, 2620, 2530,
    2558};
inline bool prime(int x) {
  if (x < 2) return 0;
  int j = 2;
  while (j * j <= x) {
    if (x % j == 0) {
      return 0;
    }
    if (j == 2)
      j++;
    else
      j += 2;
  }
  return 1;
}
inline int ans(int x) {
  int j = x / 100000;
  int ret = 0;
  if (x >= 2) ret++;
  for (int i = 0; i <= j; ++i) {
    ret += f[i];
  }
  if (j > 0) ret--;
  int b = j * 100000;
  b++;
  for (int i = b; i <= x; i += 4) {
    if (prime(i)) ret++;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> l >> r;
  cout << ans(r) - ans(l - 1) << endl;
  return 0;
}

```