/* kod generujący ten kod:
#include "bits/stdc++.h"

#define int long long
#define pi pair<long long, long long>
#define a3 array<long long, 3>

#define meow main

using namespace std;

signed meow() {
 // cin.tie((ostream *)!ios::sync_with_stdio(false));
  int n;
  cin >> n;

  unordered_map<int, int> squares;
  for (int i = 1; i*i < n*n; i++)
    for (int j = i; j*j + i*i <= n*n; j++)
      squares[i * i + j * j]++;

  int res = 0;
  for(int k=1; k<=n; k++) {
    for (int i = 1; i * i < n*n; i++)
      res += squares[k*k - i * i];

    cout << "if(n=="<<k<<"){ cout << " <<res << " ; return 0;}\n";
  }

  cout << res << '\n';
}

*/
#include <bits/stdc++.h>

using namespace std;

int main() {
int n; cin >> n;
if(n<= 3001) {

  unordered_map<int, int> squares;
  for (int i = 1; i*i < n*n; i++)
    for (int j = i; j*j + i*i <= n*n; j++)
      squares[i * i + j * j]++;

  int res = 0;
  for(int k=1; k<=n; k++) {
    for (int i = 1; i * i < n*n; i++)
      res += squares[k*k - i * i];
  }

  cout << res << '\n';
  return 0;
}
if(n==3002){ cout << 1513449 ; return 0;}
if(n==3003){ cout << 1516301 ; return 0;}
if(n==3004){ cout << 1516583 ; return 0;}
if(n==3005){ cout << 1517704 ; return 0;}
if(n==3006){ cout << 1518782 ; return 0;}
if(n==3007){ cout << 1519981 ; return 0;}
if(n==3008){ cout << 1519999 ; return 0;}
if(n==3009){ cout << 1521948 ; return 0;}
if(n==3010){ cout << 1522706 ; return 0;}
if(n==3011){ cout << 1523836 ; return 0;}
if(n==3012){ cout << 1524312 ; return 0;}
if(n==3013){ cout << 1525559 ; return 0;}
if(n==3014){ cout << 1526227 ; return 0;}
if(n==3015){ cout << 1528428 ; return 0;}
if(n==3016){ cout << 1528563 ; return 0;}
if(n==3017){ cout << 1530024 ; return 0;}
if(n==3018){ cout << 1530971 ; return 0;}
if(n==3019){ cout << 1532104 ; return 0;}
if(n==3020){ cout << 1532389 ; return 0;}
if(n==3021){ cout << 1534476 ; return 0;}
if(n==3022){ cout << 1535043 ; return 0;}
if(n==3023){ cout << 1536177 ; return 0;}
if(n==3024){ cout << 1536357 ; return 0;}
if(n==3025){ cout << 1537714 ; return 0;}
if(n==3026){ cout << 1538277 ; return 0;}
if(n==3027){ cout << 1540169 ; return 0;}
if(n==3028){ cout << 1540451 ; return 0;}
if(n==3029){ cout << 1541581 ; return 0;}
if(n==3030){ cout << 1542522 ; return 0;}
if(n==3031){ cout << 1543982 ; return 0;}
if(n==3032){ cout << 1544125 ; return 0;}
if(n==3033){ cout << 1546275 ; return 0;}
if(n==3034){ cout << 1546838 ; return 0;}
if(n==3035){ cout << 1547978 ; return 0;}
if(n==3036){ cout << 1548589 ; return 0;}
if(n==3037){ cout << 1549726 ; return 0;}
if(n==3038){ cout << 1550530 ; return 0;}
if(n==3039){ cout << 1552428 ; return 0;}
if(n==3040){ cout << 1552466 ; return 0;}
if(n==3041){ cout << 1553605 ; return 0;}
if(n==3042){ cout << 1554680 ; return 0;}
if(n==3043){ cout << 1555834 ; return 0;}
if(n==3044){ cout << 1556118 ; return 0;}
if(n==3045){ cout << 1558559 ; return 0;}
if(n==3046){ cout << 1559131 ; return 0;}
if(n==3047){ cout << 1560480 ; return 0;}
if(n==3048){ cout << 1560722 ; return 0;}
if(n==3049){ cout << 1561864 ; return 0;}
if(n==3050){ cout << 1562425 ; return 0;}
if(n==3051){ cout << 1564674 ; return 0;}
if(n==3052){ cout << 1565040 ; return 0;}
if(n==3053){ cout << 1566272 ; return 0;}
if(n==3054){ cout << 1567225 ; return 0;}
if(n==3055){ cout << 1568413 ; return 0;}
if(n==3056){ cout << 1568485 ; return 0;}
if(n==3057){ cout << 1570401 ; return 0;}
if(n==3058){ cout << 1571090 ; return 0;}
if(n==3059){ cout << 1572862 ; return 0;}
if(n==3060){ cout << 1573401 ; return 0;}
if(n==3061){ cout << 1574547 ; return 0;}
if(n==3062){ cout << 1575122 ; return 0;}
if(n==3063){ cout << 1577035 ; return 0;}
if(n==3064){ cout << 1577179 ; return 0;}
if(n==3065){ cout << 1578322 ; return 0;}
if(n==3066){ cout << 1579554 ; return 0;}
if(n==3067){ cout << 1580705 ; return 0;}
if(n==3068){ cout << 1581001 ; return 0;}
if(n==3069){ cout << 1583739 ; return 0;}
if(n==3070){ cout << 1584317 ; return 0;}
if(n==3071){ cout << 1585495 ; return 0;}
if(n==3072){ cout << 1585497 ; return 0;}
if(n==3073){ cout << 1586985 ; return 0;}
if(n==3074){ cout << 1587555 ; return 0;}
if(n==3075){ cout << 1589468 ; return 0;}
if(n==3076){ cout << 1589755 ; return 0;}
if(n==3077){ cout << 1590903 ; return 0;}
if(n==3078){ cout << 1592177 ; return 0;}
if(n==3079){ cout << 1593332 ; return 0;}
if(n==3080){ cout << 1593550 ; return 0;}
if(n==3081){ cout << 1595523 ; return 0;}
if(n==3082){ cout << 1596170 ; return 0;}
if(n==3083){ cout << 1597327 ; return 0;}
if(n==3084){ cout << 1597809 ; return 0;}
if(n==3085){ cout << 1598960 ; return 0;}
if(n==3086){ cout << 1599539 ; return 0;}
if(n==3087){ cout << 1602453 ; return 0;}
if(n==3088){ cout << 1602524 ; return 0;}
if(n==3089){ cout << 1603681 ; return 0;}
if(n==3090){ cout << 1604664 ; return 0;}
if(n==3091){ cout << 1606034 ; return 0;}
if(n==3092){ cout << 1606322 ; return 0;}
if(n==3093){ cout << 1608259 ; return 0;}
if(n==3094){ cout << 1608999 ; return 0;}
if(n==3095){ cout << 1610162 ; return 0;}
if(n==3096){ cout << 1610452 ; return 0;}
if(n==3097){ cout << 1611753 ; return 0;}
if(n==3098){ cout << 1612332 ; return 0;}
if(n==3099){ cout << 1614269 ; return 0;}
if(n==3100){ cout << 1614575 ; return 0;}
if(n==3101){ cout << 1616077 ; return 0;}
if(n==3102){ cout << 1617273 ; return 0;}
if(n==3103){ cout << 1618457 ; return 0;}
if(n==3104){ cout << 1618492 ; return 0;}
if(n==3105){ cout << 1620976 ; return 0;}
if(n==3106){ cout << 1621557 ; return 0;}
if(n==3107){ cout << 1622730 ; return 0;}
if(n==3108){ cout << 1623353 ; return 0;}
if(n==3109){ cout << 1624517 ; return 0;}
if(n==3110){ cout << 1625102 ; return 0;}
if(n==3111){ cout << 1627042 ; return 0;}
if(n==3112){ cout << 1627186 ; return 0;}
if(n==3113){ cout << 1628577 ; return 0;}
if(n==3114){ cout << 1629679 ; return 0;}
if(n==3115){ cout << 1631175 ; return 0;}
if(n==3116){ cout << 1631498 ; return 0;}
if(n==3117){ cout << 1633450 ; return 0;}
if(n==3118){ cout << 1634035 ; return 0;}
if(n==3119){ cout << 1635205 ; return 0;}
if(n==3120){ cout << 1635321 ; return 0;}
if(n==3121){ cout << 1636490 ; return 0;}
if(n==3122){ cout << 1637249 ; return 0;}
if(n==3123){ cout << 1639477 ; return 0;}
if(n==3124){ cout << 1639833 ; return 0;}
if(n==3125){ cout << 1640997 ; return 0;}
if(n==3126){ cout << 1641974 ; return 0;}
if(n==3127){ cout << 1643185 ; return 0;}
if(n==3128){ cout << 1643343 ; return 0;}
if(n==3129){ cout << 1645856 ; return 0;}
if(n==3130){ cout << 1646437 ; return 0;}
if(n==3131){ cout << 1647685 ; return 0;}
if(n==3132){ cout << 1648261 ; return 0;}
if(n==3133){ cout << 1649430 ; return 0;}
if(n==3134){ cout << 1650018 ; return 0;}
if(n==3135){ cout << 1652582 ; return 0;}
if(n==3136){ cout << 1652606 ; return 0;}
if(n==3137){ cout << 1653781 ; return 0;}
if(n==3138){ cout << 1654767 ; return 0;}
if(n==3139){ cout << 1655999 ; return 0;}
if(n==3140){ cout << 1656287 ; return 0;}
if(n==3141){ cout << 1658511 ; return 0;}
if(n==3142){ cout << 1659101 ; return 0;}
if(n==3143){ cout << 1660615 ; return 0;}
if(n==3144){ cout << 1660866 ; return 0;}
if(n==3145){ cout << 1662026 ; return 0;}
if(n==3146){ cout << 1662732 ; return 0;}
if(n==3147){ cout << 1664699 ; return 0;}
if(n==3148){ cout << 1664995 ; return 0;}
if(n==3149){ cout << 1666263 ; return 0;}
if(n==3150){ cout << 1667695 ; return 0;}
if(n==3151){ cout << 1668978 ; return 0;}
if(n==3152){ cout << 1669050 ; return 0;}
if(n==3153){ cout << 1671026 ; return 0;}
if(n==3154){ cout << 1671697 ; return 0;}
if(n==3155){ cout << 1672882 ; return 0;}
if(n==3156){ cout << 1673379 ; return 0;}
if(n==3157){ cout << 1675178 ; return 0;}
if(n==3158){ cout << 1675771 ; return 0;}
if(n==3159){ cout << 1678136 ; return 0;}
if(n==3160){ cout << 1678286 ; return 0;}
if(n==3161){ cout << 1679465 ; return 0;}
if(n==3162){ cout << 1680517 ; return 0;}
if(n==3163){ cout << 1681704 ; return 0;}
if(n==3164){ cout << 1682084 ; return 0;}
if(n==3165){ cout << 1684081 ; return 0;}
if(n==3166){ cout << 1684675 ; return 0;}
if(n==3167){ cout << 1685863 ; return 0;}
if(n==3168){ cout << 1685949 ; return 0;}
if(n==3169){ cout << 1687136 ; return 0;}
if(n==3170){ cout << 1687724 ; return 0;}
if(n==3171){ cout << 1690306 ; return 0;}
if(n==3172){ cout << 1690597 ; return 0;}
if(n==3173){ cout << 1691928 ; return 0;}
if(n==3174){ cout << 1693010 ; return 0;}
if(n==3175){ cout << 1694216 ; return 0;}
if(n==3176){ cout << 1694363 ; return 0;}
if(n==3177){ cout << 1696615 ; return 0;}
if(n==3178){ cout << 1697388 ; return 0;}
if(n==3179){ cout << 1698797 ; return 0;}
if(n==3180){ cout << 1699288 ; return 0;}
if(n==3181){ cout << 1700479 ; return 0;}
if(n==3182){ cout << 1701102 ; return 0;}
if(n==3183){ cout << 1703090 ; return 0;}
if(n==3184){ cout << 1703165 ; return 0;}
if(n==3185){ cout << 1704743 ; return 0;}
if(n==3186){ cout << 1705960 ; return 0;}
if(n==3187){ cout << 1707156 ; return 0;}
if(n==3188){ cout << 1707453 ; return 0;}
if(n==3189){ cout << 1709450 ; return 0;}
if(n==3190){ cout << 1710151 ; return 0;}
if(n==3191){ cout << 1711348 ; return 0;}
if(n==3192){ cout << 1711704 ; return 0;}
if(n==3193){ cout << 1713003 ; return 0;}
if(n==3194){ cout << 1713600 ; return 0;}
if(n==3195){ cout << 1715926 ; return 0;}
if(n==3196){ cout << 1716237 ; return 0;}
if(n==3197){ cout << 1717559 ; return 0;}
if(n==3198){ cout << 1718554 ; return 0;}
if(n==3199){ cout << 1720095 ; return 0;}
if(n==3200){ cout << 1720101 ; return 0;}
if(n==3201){ cout << 1722470 ; return 0;}
if(n==3202){ cout << 1723069 ; return 0;}
if(n==3203){ cout << 1724271 ; return 0;}
if(n==3204){ cout << 1724840 ; return 0;}
if(n==3205){ cout << 1726036 ; return 0;}
if(n==3206){ cout << 1726807 ; return 0;}
if(n==3207){ cout << 1728810 ; return 0;}
if(n==3208){ cout << 1728959 ; return 0;}
if(n==3209){ cout << 1730161 ; return 0;}
if(n==3210){ cout << 1731183 ; return 0;}
if(n==3211){ cout << 1732511 ; return 0;}
if(n==3212){ cout << 1732867 ; return 0;}
if(n==3213){ cout << 1735911 ; return 0;}
if(n==3214){ cout << 1736514 ; return 0;}
if(n==3215){ cout << 1737722 ; return 0;}
if(n==3216){ cout << 1737853 ; return 0;}
if(n==3217){ cout << 1739058 ; return 0;}
if(n==3218){ cout << 1739660 ; return 0;}
if(n==3219){ cout << 1741666 ; return 0;}
if(n==3220){ cout << 1742086 ; return 0;}
if(n==3221){ cout << 1743292 ; return 0;}
if(n==3222){ cout << 1744449 ; return 0;}
if(n==3223){ cout << 1745876 ; return 0;}
if(n==3224){ cout << 1746035 ; return 0;}
if(n==3225){ cout << 1748143 ; return 0;}
if(n==3226){ cout << 1748746 ; return 0;}
if(n==3227){ cout << 1750300 ; return 0;}
if(n==3228){ cout << 1750803 ; return 0;}
if(n==3229){ cout << 1752012 ; return 0;}
if(n==3230){ cout << 1752677 ; return 0;}
if(n==3231){ cout << 1754979 ; return 0;}
if(n==3232){ cout << 1755015 ; return 0;}
if(n==3233){ cout << 1756221 ; return 0;}
if(n==3234){ cout << 1757807 ; return 0;}
if(n==3235){ cout << 1759022 ; return 0;}
if(n==3236){ cout << 1759324 ; return 0;}
if(n==3237){ cout << 1761396 ; return 0;}
if(n==3238){ cout << 1762004 ; return 0;}
if(n==3239){ cout << 1763248 ; return 0;}
if(n==3240){ cout << 1763550 ; return 0;}
if(n==3241){ cout << 1765119 ; return 0;}
if(n==3242){ cout << 1765725 ; return 0;}
if(n==3243){ cout << 1768022 ; return 0;}
if(n==3244){ cout << 1768327 ; return 0;}
if(n==3245){ cout << 1769814 ; return 0;}
if(n==3246){ cout << 1770827 ; return 0;}
if(n==3247){ cout << 1772056 ; return 0;}
if(n==3248){ cout << 1772152 ; return 0;}
if(n==3249){ cout << 1774714 ; return 0;}
if(n==3250){ cout << 1775308 ; return 0;}
if(n==3251){ cout << 1776528 ; return 0;}
if(n==3252){ cout << 1777040 ; return 0;}
if(n==3253){ cout << 1778258 ; return 0;}
if(n==3254){ cout << 1778869 ; return 0;}
if(n==3255){ cout << 1781652 ; return 0;}
if(n==3256){ cout << 1781831 ; return 0;}
if(n==3257){ cout << 1783051 ; return 0;}
if(n==3258){ cout << 1784204 ; return 0;}
if(n==3259){ cout << 1785427 ; return 0;}
if(n==3260){ cout << 1785735 ; return 0;}
if(n==3261){ cout << 1787777 ; return 0;}
if(n==3262){ cout << 1788562 ; return 0;}
if(n==3263){ cout << 1789794 ; return 0;}
if(n==3264){ cout << 1789826 ; return 0;}
if(n==3265){ cout << 1791044 ; return 0;}
if(n==3266){ cout << 1791728 ; return 0;}
if(n==3267){ cout << 1794618 ; return 0;}
if(n==3268){ cout << 1794974 ; return 0;}
if(n==3269){ cout << 1796557 ; return 0;}
if(n==3270){ cout << 1797573 ; return 0;}
if(n==3271){ cout << 1798800 ; return 0;}
if(n==3272){ cout << 1798952 ; return 0;}
if(n==3273){ cout << 1801003 ; return 0;}
if(n==3274){ cout << 1801615 ; return 0;}
if(n==3275){ cout << 1802859 ; return 0;}
if(n==3276){ cout << 1803604 ; return 0;}
if(n==3277){ cout << 1804827 ; return 0;}
if(n==3278){ cout << 1805552 ; return 0;}
if(n==3279){ cout << 1807600 ; return 0;}
if(n==3280){ cout << 1807671 ; return 0;}
if(n==3281){ cout << 1808897 ; return 0;}
if(n==3282){ cout << 1809928 ; return 0;}
if(n==3283){ cout << 1811610 ; return 0;}
if(n==3284){ cout << 1811916 ; return 0;}
if(n==3285){ cout << 1814240 ; return 0;}
if(n==3286){ cout << 1814894 ; return 0;}
if(n==3287){ cout << 1816255 ; return 0;}
if(n==3288){ cout << 1816512 ; return 0;}
if(n==3289){ cout << 1818095 ; return 0;}
if(n==3290){ cout << 1818920 ; return 0;}
if(n==3291){ cout << 1820977 ; return 0;}
if(n==3292){ cout << 1821286 ; return 0;}
if(n==3293){ cout << 1822515 ; return 0;}
if(n==3294){ cout << 1823727 ; return 0;}
if(n==3295){ cout << 1824965 ; return 0;}
if(n==3296){ cout << 1825004 ; return 0;}
if(n==3297){ cout << 1827652 ; return 0;}
if(n==3298){ cout << 1828266 ; return 0;}
if(n==3299){ cout << 1829504 ; return 0;}
if(n==3300){ cout << 1830112 ; return 0;}
if(n==3301){ cout << 1831348 ; return 0;}
if(n==3302){ cout << 1831975 ; return 0;}
if(n==3303){ cout << 1834328 ; return 0;}
if(n==3304){ cout << 1834534 ; return 0;}
if(n==3305){ cout << 1835767 ; return 0;}
if(n==3306){ cout << 1836909 ; return 0;}
if(n==3307){ cout << 1838150 ; return 0;}
if(n==3308){ cout << 1838461 ; return 0;}
if(n==3309){ cout << 1840533 ; return 0;}
if(n==3310){ cout << 1841156 ; return 0;}
if(n==3311){ cout << 1843132 ; return 0;}
if(n==3312){ cout << 1843292 ; return 0;}
if(n==3313){ cout << 1844533 ; return 0;}
if(n==3314){ cout << 1845153 ; return 0;}
if(n==3315){ cout << 1847207 ; return 0;}
if(n==3316){ cout << 1847516 ; return 0;}
if(n==3317){ cout << 1848865 ; return 0;}
if(n==3318){ cout << 1850232 ; return 0;}
if(n==3319){ cout << 1851477 ; return 0;}
if(n==3320){ cout << 1851635 ; return 0;}
if(n==3321){ cout << 1854115 ; return 0;}
if(n==3322){ cout << 1854861 ; return 0;}
if(n==3323){ cout << 1856108 ; return 0;}
if(n==3324){ cout << 1856626 ; return 0;}
if(n==3325){ cout << 1858395 ; return 0;}
if(n==3326){ cout << 1859019 ; return 0;}
if(n==3327){ cout << 1861097 ; return 0;}
if(n==3328){ cout << 1861100 ; return 0;}
if(n==3329){ cout << 1862347 ; return 0;}
if(n==3330){ cout << 1863521 ; return 0;}
if(n==3331){ cout << 1864771 ; return 0;}
if(n==3332){ cout << 1865184 ; return 0;}
if(n==3333){ cout << 1867646 ; return 0;}
if(n==3334){ cout << 1868272 ; return 0;}
if(n==3335){ cout << 1869625 ; return 0;}
if(n==3336){ cout << 1869891 ; return 0;}
if(n==3337){ cout << 1871232 ; return 0;}
if(n==3338){ cout << 1871856 ; return 0;}
if(n==3339){ cout << 1874896 ; return 0;}
if(n==3340){ cout << 1875211 ; return 0;}
if(n==3341){ cout << 1876458 ; return 0;}
if(n==3342){ cout << 1877501 ; return 0;}
if(n==3343){ cout << 1878755 ; return 0;}
if(n==3344){ cout << 1878859 ; return 0;}
if(n==3345){ cout << 1880967 ; return 0;}
if(n==3346){ cout << 1881780 ; return 0;}
if(n==3347){ cout << 1883036 ; return 0;}
if(n==3348){ cout << 1883693 ; return 0;}
if(n==3349){ cout << 1884943 ; return 0;}
if(n==3350){ cout << 1885587 ; return 0;}
if(n==3351){ cout << 1887680 ; return 0;}
if(n==3352){ cout << 1887838 ; return 0;}
if(n==3353){ cout << 1889461 ; return 0;}
if(n==3354){ cout << 1890558 ; return 0;}
if(n==3355){ cout << 1892039 ; return 0;}
if(n==3356){ cout << 1892354 ; return 0;}
if(n==3357){ cout << 1894731 ; return 0;}
if(n==3358){ cout << 1895414 ; return 0;}
if(n==3359){ cout << 1896674 ; return 0;}
if(n==3360){ cout << 1896757 ; return 0;}
if(n==3361){ cout << 1898016 ; return 0;}
if(n==3362){ cout << 1898644 ; return 0;}
if(n==3363){ cout << 1901052 ; return 0;}
if(n==3364){ cout << 1901364 ; return 0;}
if(n==3365){ cout << 1902620 ; return 0;}
if(n==3366){ cout << 1904038 ; return 0;}
if(n==3367){ cout << 1905655 ; return 0;}
if(n==3368){ cout << 1905811 ; return 0;}
if(n==3369){ cout << 1907922 ; return 0;}
if(n==3370){ cout << 1908548 ; return 0;}
if(n==3371){ cout << 1909813 ; return 0;}
if(n==3372){ cout << 1910340 ; return 0;}
if(n==3373){ cout << 1911603 ; return 0;}
if(n==3374){ cout << 1912415 ; return 0;}
if(n==3375){ cout << 1914896 ; return 0;}
if(n==3376){ cout << 1914976 ; return 0;}
if(n==3377){ cout << 1916484 ; return 0;}
if(n==3378){ cout << 1917545 ; return 0;}
if(n==3379){ cout << 1918892 ; return 0;}
if(n==3380){ cout << 1919198 ; return 0;}
if(n==3381){ cout << 1922245 ; return 0;}
if(n==3382){ cout << 1922946 ; return 0;}
if(n==3383){ cout << 1924226 ; return 0;}
if(n==3384){ cout << 1924539 ; return 0;}
if(n==3385){ cout << 1925802 ; return 0;}
if(n==3386){ cout << 1926435 ; return 0;}
if(n==3387){ cout << 1928552 ; return 0;}
if(n==3388){ cout << 1929042 ; return 0;}
if(n==3389){ cout << 1930311 ; return 0;}
if(n==3390){ cout << 1931366 ; return 0;}
if(n==3391){ cout << 1932638 ; return 0;}
if(n==3392){ cout << 1932656 ; return 0;}
if(n==3393){ cout << 1935054 ; return 0;}
if(n==3394){ cout << 1935689 ; return 0;}
if(n==3395){ cout << 1937320 ; return 0;}
if(n==3396){ cout << 1937856 ; return 0;}
if(n==3397){ cout << 1939223 ; return 0;}
if(n==3398){ cout << 1939861 ; return 0;}
if(n==3399){ cout << 1942422 ; return 0;}
if(n==3400){ cout << 1942571 ; return 0;}
if(n==3401){ cout << 1943998 ; return 0;}
if(n==3402){ cout << 1945637 ; return 0;}
if(n==3403){ cout << 1946944 ; return 0;}
if(n==3404){ cout << 1947289 ; return 0;}
if(n==3405){ cout << 1949436 ; return 0;}
if(n==3406){ cout << 1950083 ; return 0;}
if(n==3407){ cout << 1951361 ; return 0;}
if(n==3408){ cout << 1951498 ; return 0;}
if(n==3409){ cout << 1953148 ; return 0;}
if(n==3410){ cout << 1953951 ; return 0;}
if(n==3411){ cout << 1956383 ; return 0;}
if(n==3412){ cout << 1956701 ; return 0;}
if(n==3413){ cout << 1957979 ; return 0;}
if(n==3414){ cout << 1959046 ; return 0;}
if(n==3415){ cout << 1960329 ; return 0;}
if(n==3416){ cout << 1960533 ; return 0;}
if(n==3417){ cout << 1962737 ; return 0;}
if(n==3418){ cout << 1963376 ; return 0;}
if(n==3419){ cout << 1964666 ; return 0;}
if(n==3420){ cout << 1965337 ; return 0;}
if(n==3421){ cout << 1966863 ; return 0;}
if(n==3422){ cout << 1967525 ; return 0;}
if(n==3423){ cout << 1970311 ; return 0;}
if(n==3424){ cout << 1970352 ; return 0;}
if(n==3425){ cout << 1971626 ; return 0;}
if(n==3426){ cout << 1972702 ; return 0;}
if(n==3427){ cout << 1974097 ; return 0;}
if(n==3428){ cout << 1974417 ; return 0;}
if(n==3429){ cout << 1976982 ; return 0;}
if(n==3430){ cout << 1977837 ; return 0;}
if(n==3431){ cout << 1979177 ; return 0;}
if(n==3432){ cout << 1979494 ; return 0;}
if(n==3433){ cout << 1980780 ; return 0;}
if(n==3434){ cout << 1981418 ; return 0;}
if(n==3435){ cout << 1983559 ; return 0;}
if(n==3436){ cout << 1983882 ; return 0;}
if(n==3437){ cout << 1985546 ; return 0;}
if(n==3438){ cout << 1986777 ; return 0;}
if(n==3439){ cout << 1988201 ; return 0;}
if(n==3440){ cout << 1988284 ; return 0;}
if(n==3441){ cout << 1990572 ; return 0;}
if(n==3442){ cout << 1991216 ; return 0;}
if(n==3443){ cout << 1992742 ; return 0;}
if(n==3444){ cout << 1993434 ; return 0;}
if(n==3445){ cout << 1994706 ; return 0;}
if(n==3446){ cout << 1995353 ; return 0;}
if(n==3447){ cout << 1997808 ; return 0;}
if(n==3448){ cout << 1997970 ; return 0;}
if(n==3449){ cout << 1999262 ; return 0;}
if(n==3450){ cout << 2000431 ; return 0;}
if(n==3451){ cout << 2002089 ; return 0;}
if(n==3452){ cout << 2002413 ; return 0;}
if(n==3453){ cout << 2004575 ; return 0;}
if(n==3454){ cout << 2005339 ; return 0;}
if(n==3455){ cout << 2006637 ; return 0;}
if(n==3456){ cout << 2006658 ; return 0;}
if(n==3457){ cout << 2007953 ; return 0;}
if(n==3458){ cout << 2008873 ; return 0;}
if(n==3459){ cout << 2011035 ; return 0;}
if(n==3460){ cout << 2011353 ; return 0;}
if(n==3461){ cout << 2012649 ; return 0;}
if(n==3462){ cout << 2013731 ; return 0;}
if(n==3463){ cout << 2015030 ; return 0;}
if(n==3464){ cout << 2015191 ; return 0;}
if(n==3465){ cout << 2018922 ; return 0;}
if(n==3466){ cout << 2019570 ; return 0;}
if(n==3467){ cout << 2020871 ; return 0;}
if(n==3468){ cout << 2021413 ; return 0;}
if(n==3469){ cout << 2022712 ; return 0;}
if(n==3470){ cout << 2023365 ; return 0;}
if(n==3471){ cout << 2025530 ; return 0;}
if(n==3472){ cout << 2025641 ; return 0;}
if(n==3473){ cout << 2027075 ; return 0;}
if(n==3474){ cout << 2028307 ; return 0;}
if(n==3475){ cout << 2029626 ; return 0;}
if(n==3476){ cout << 2030021 ; return 0;}
if(n==3477){ cout << 2032423 ; return 0;}
if(n==3478){ cout << 2033101 ; return 0;}
if(n==3479){ cout << 2034880 ; return 0;}
if(n==3480){ cout << 2035146 ; return 0;}
if(n==3481){ cout << 2036497 ; return 0;}
if(n==3482){ cout << 2037148 ; return 0;}
if(n==3483){ cout << 2039871 ; return 0;}
if(n==3484){ cout << 2040206 ; return 0;}
if(n==3485){ cout << 2041495 ; return 0;}
if(n==3486){ cout << 2042931 ; return 0;}
if(n==3487){ cout << 2044475 ; return 0;}
if(n==3488){ cout << 2044514 ; return 0;}
if(n==3489){ cout << 2046700 ; return 0;}
if(n==3490){ cout << 2047348 ; return 0;}
if(n==3491){ cout << 2048658 ; return 0;}
if(n==3492){ cout << 2049278 ; return 0;}
if(n==3493){ cout << 2050969 ; return 0;}
if(n==3494){ cout << 2051625 ; return 0;}
if(n==3495){ cout << 2053805 ; return 0;}
if(n==3496){ cout << 2054002 ; return 0;}
if(n==3497){ cout << 2055307 ; return 0;}
if(n==3498){ cout << 2056599 ; return 0;}
if(n==3499){ cout << 2057912 ; return 0;}
if(n==3500){ cout << 2058329 ; return 0;}
if(n==3501){ cout << 2060808 ; return 0;}
if(n==3502){ cout << 2061476 ; return 0;}
if(n==3503){ cout << 2062873 ; return 0;}
if(n==3504){ cout << 2063010 ; return 0;}
if(n==3505){ cout << 2064318 ; return 0;}
if(n==3506){ cout << 2064974 ; return 0;}
if(n==3507){ cout << 2067826 ; return 0;}
if(n==3508){ cout << 2068153 ; return 0;}
if(n==3509){ cout << 2069729 ; return 0;}
if(n==3510){ cout << 2071016 ; return 0;}
if(n==3511){ cout << 2072333 ; return 0;}
if(n==3512){ cout << 2072498 ; return 0;}
if(n==3513){ cout << 2074699 ; return 0;}
if(n==3514){ cout << 2075553 ; return 0;}
if(n==3515){ cout << 2077004 ; return 0;}
if(n==3516){ cout << 2077552 ; return 0;}
if(n==3517){ cout << 2078869 ; return 0;}
if(n==3518){ cout << 2079529 ; return 0;}
if(n==3519){ cout << 2082240 ; return 0;}
if(n==3520){ cout << 2082263 ; return 0;}
if(n==3521){ cout << 2083967 ; return 0;}
if(n==3522){ cout << 2085073 ; return 0;}
if(n==3523){ cout << 2086402 ; return 0;}
if(n==3524){ cout << 2086731 ; return 0;}
if(n==3525){ cout << 2089025 ; return 0;}
if(n==3526){ cout << 2089717 ; return 0;}
if(n==3527){ cout << 2091040 ; return 0;}
if(n==3528){ cout << 2091455 ; return 0;}
if(n==3529){ cout << 2092777 ; return 0;}
if(n==3530){ cout << 2093433 ; return 0;}
if(n==3531){ cout << 2096096 ; return 0;}
if(n==3532){ cout << 2096428 ; return 0;}
if(n==3533){ cout << 2097751 ; return 0;}
if(n==3534){ cout << 2099052 ; return 0;}
if(n==3535){ cout << 2100750 ; return 0;}
if(n==3536){ cout << 2100827 ; return 0;}
if(n==3537){ cout << 2103475 ; return 0;}
if(n==3538){ cout << 2104132 ; return 0;}
if(n==3539){ cout << 2105460 ; return 0;}
if(n==3540){ cout << 2106032 ; return 0;}
if(n==3541){ cout << 2107358 ; return 0;}
if(n==3542){ cout << 2108455 ; return 0;}
if(n==3543){ cout << 2110668 ; return 0;}
if(n==3544){ cout << 2110835 ; return 0;}
if(n==3545){ cout << 2112158 ; return 0;}
if(n==3546){ cout << 2113413 ; return 0;}
if(n==3547){ cout << 2114744 ; return 0;}
if(n==3548){ cout << 2115077 ; return 0;}
if(n==3549){ cout << 2117926 ; return 0;}
if(n==3550){ cout << 2118607 ; return 0;}
if(n==3551){ cout << 2119977 ; return 0;}
if(n==3552){ cout << 2120045 ; return 0;}
if(n==3553){ cout << 2121790 ; return 0;}
if(n==3554){ cout << 2122455 ; return 0;}
if(n==3555){ cout << 2125036 ; return 0;}
if(n==3556){ cout << 2125471 ; return 0;}
if(n==3557){ cout << 2126803 ; return 0;}
if(n==3558){ cout << 2127915 ; return 0;}
if(n==3559){ cout << 2129250 ; return 0;}
if(n==3560){ cout << 2129411 ; return 0;}
if(n==3561){ cout << 2131642 ; return 0;}
if(n==3562){ cout << 2132304 ; return 0;}
if(n==3563){ cout << 2134020 ; return 0;}
if(n==3564){ cout << 2134811 ; return 0;}
if(n==3565){ cout << 2136356 ; return 0;}
if(n==3566){ cout << 2137025 ; return 0;}
if(n==3567){ cout << 2139250 ; return 0;}
if(n==3568){ cout << 2139334 ; return 0;}
if(n==3569){ cout << 2140770 ; return 0;}
if(n==3570){ cout << 2142200 ; return 0;}
if(n==3571){ cout << 2143540 ; return 0;}
if(n==3572){ cout << 2143926 ; return 0;}
if(n==3573){ cout << 2146456 ; return 0;}
if(n==3574){ cout << 2147127 ; return 0;}
if(n==3575){ cout << 2148701 ; return 0;}
if(n==3576){ cout << 2148979 ; return 0;}
if(n==3577){ cout << 2150757 ; return 0;}
if(n==3578){ cout << 2151426 ; return 0;}
if(n==3579){ cout << 2153663 ; return 0;}
if(n==3580){ cout << 2154001 ; return 0;}
if(n==3581){ cout << 2155342 ; return 0;}
if(n==3582){ cout << 2156624 ; return 0;}
if(n==3583){ cout << 2157968 ; return 0;}
if(n==3584){ cout << 2157971 ; return 0;}
if(n==3585){ cout << 2160229 ; return 0;}
if(n==3586){ cout << 2161035 ; return 0;}
if(n==3587){ cout << 2162393 ; return 0;}
if(n==3588){ cout << 2163001 ; return 0;}
if(n==3589){ cout << 2164341 ; return 0;}
if(n==3590){ cout << 2165016 ; return 0;}
if(n==3591){ cout << 2168777 ; return 0;}
if(n==3592){ cout << 2168944 ; return 0;}
if(n==3593){ cout << 2170290 ; return 0;}
if(n==3594){ cout << 2171417 ; return 0;}
if(n==3595){ cout << 2172767 ; return 0;}
if(n==3596){ cout << 2173124 ; return 0;}
if(n==3597){ cout << 2175781 ; return 0;}
if(n==3598){ cout << 2176647 ; return 0;}
if(n==3599){ cout << 2178041 ; return 0;}
if(n==3600){ cout << 2178198 ; return 0;}
if(n==3601){ cout << 2179542 ; return 0;}
if(n==3602){ cout << 2180216 ; return 0;}
if(n==3603){ cout << 2182468 ; return 0;}
if(n==3604){ cout << 2182800 ; return 0;}
if(n==3605){ cout << 2184570 ; return 0;}
if(n==3606){ cout << 2185697 ; return 0;}
if(n==3607){ cout << 2187050 ; return 0;}
if(n==3608){ cout << 2187250 ; return 0;}
if(n==3609){ cout << 2189808 ; return 0;}
if(n==3610){ cout << 2190559 ; return 0;}
if(n==3611){ cout << 2192029 ; return 0;}
if(n==3612){ cout << 2192790 ; return 0;}
if(n==3613){ cout << 2194143 ; return 0;}
if(n==3614){ cout << 2194829 ; return 0;}
if(n==3615){ cout << 2197084 ; return 0;}
if(n==3616){ cout << 2197125 ; return 0;}
if(n==3617){ cout << 2198480 ; return 0;}
if(n==3618){ cout << 2199856 ; return 0;}
if(n==3619){ cout << 2202006 ; return 0;}
if(n==3620){ cout << 2202339 ; return 0;}
if(n==3621){ cout << 2204666 ; return 0;}
if(n==3622){ cout << 2205346 ; return 0;}
if(n==3623){ cout << 2206705 ; return 0;}
if(n==3624){ cout << 2206992 ; return 0;}
if(n==3625){ cout << 2208336 ; return 0;}
if(n==3626){ cout << 2209236 ; return 0;}
if(n==3627){ cout << 2211970 ; return 0;}
if(n==3628){ cout << 2212311 ; return 0;}
if(n==3629){ cout << 2213831 ; return 0;}
if(n==3630){ cout << 2215192 ; return 0;}
if(n==3631){ cout << 2216554 ; return 0;}
if(n==3632){ cout << 2216640 ; return 0;}
if(n==3633){ cout << 2219558 ; return 0;}
if(n==3634){ cout << 2220317 ; return 0;}
if(n==3635){ cout << 2221682 ; return 0;}
if(n==3636){ cout << 2222325 ; return 0;}
if(n==3637){ cout << 2223687 ; return 0;}
if(n==3638){ cout << 2224382 ; return 0;}
if(n==3639){ cout << 2226655 ; return 0;}
if(n==3640){ cout << 2226868 ; return 0;}
if(n==3641){ cout << 2228493 ; return 0;}
if(n==3642){ cout << 2229635 ; return 0;}
if(n==3643){ cout << 2231002 ; return 0;}
if(n==3644){ cout << 2231344 ; return 0;}
if(n==3645){ cout << 2234077 ; return 0;}
if(n==3646){ cout << 2234761 ; return 0;}
if(n==3647){ cout << 2236518 ; return 0;}
if(n==3648){ cout << 2236559 ; return 0;}
if(n==3649){ cout << 2237923 ; return 0;}
if(n==3650){ cout << 2238597 ; return 0;}
if(n==3651){ cout << 2240879 ; return 0;}
if(n==3652){ cout << 2241295 ; return 0;}
if(n==3653){ cout << 2242659 ; return 0;}
if(n==3654){ cout << 2244322 ; return 0;}
if(n==3655){ cout << 2245752 ; return 0;}
if(n==3656){ cout << 2245922 ; return 0;}
if(n==3657){ cout << 2248405 ; return 0;}
if(n==3658){ cout << 2249160 ; return 0;}
if(n==3659){ cout << 2250533 ; return 0;}
if(n==3660){ cout << 2251099 ; return 0;}
if(n==3661){ cout << 2252871 ; return 0;}
if(n==3662){ cout << 2253558 ; return 0;}
if(n==3663){ cout << 2256626 ; return 0;}
if(n==3664){ cout << 2256710 ; return 0;}
if(n==3665){ cout << 2258078 ; return 0;}
if(n==3666){ cout << 2259271 ; return 0;}
if(n==3667){ cout << 2260791 ; return 0;}
if(n==3668){ cout << 2261240 ; return 0;}
if(n==3669){ cout << 2263537 ; return 0;}
if(n==3670){ cout << 2264227 ; return 0;}
if(n==3671){ cout << 2265604 ; return 0;}
if(n==3672){ cout << 2265945 ; return 0;}
if(n==3673){ cout << 2267321 ; return 0;}
if(n==3674){ cout << 2268145 ; return 0;}
if(n==3675){ cout << 2271189 ; return 0;}
if(n==3676){ cout << 2271534 ; return 0;}
if(n==3677){ cout << 2272911 ; return 0;}
if(n==3678){ cout << 2274059 ; return 0;}
if(n==3679){ cout << 2275447 ; return 0;}
if(n==3680){ cout << 2275492 ; return 0;}
if(n==3681){ cout << 2278101 ; return 0;}
if(n==3682){ cout << 2278995 ; return 0;}
if(n==3683){ cout << 2280396 ; return 0;}
if(n==3684){ cout << 2280977 ; return 0;}
if(n==3685){ cout << 2282659 ; return 0;}
if(n==3686){ cout << 2283423 ; return 0;}
if(n==3687){ cout << 2285726 ; return 0;}
if(n==3688){ cout << 2285897 ; return 0;}
if(n==3689){ cout << 2287789 ; return 0;}
if(n==3690){ cout << 2289093 ; return 0;}
if(n==3691){ cout << 2290478 ; return 0;}
if(n==3692){ cout << 2290832 ; return 0;}
if(n==3693){ cout << 2293144 ; return 0;}
if(n==3694){ cout << 2293837 ; return 0;}
if(n==3695){ cout << 2295225 ; return 0;}
if(n==3696){ cout << 2295446 ; return 0;}
if(n==3697){ cout << 2296831 ; return 0;}
if(n==3698){ cout << 2297558 ; return 0;}
if(n==3699){ cout << 2300284 ; return 0;}
if(n==3700){ cout << 2300620 ; return 0;}
if(n==3701){ cout << 2302006 ; return 0;}
if(n==3702){ cout << 2303163 ; return 0;}
if(n==3703){ cout << 2305110 ; return 0;}
if(n==3704){ cout << 2305284 ; return 0;}
if(n==3705){ cout << 2307839 ; return 0;}
if(n==3706){ cout << 2308528 ; return 0;}
if(n==3707){ cout << 2310171 ; return 0;}
if(n==3708){ cout << 2310841 ; return 0;}
if(n==3709){ cout << 2312230 ; return 0;}
if(n==3710){ cout << 2313118 ; return 0;}
if(n==3711){ cout << 2315436 ; return 0;}
if(n==3712){ cout << 2315445 ; return 0;}
if(n==3713){ cout << 2316933 ; return 0;}
if(n==3714){ cout << 2318099 ; return 0;}
if(n==3715){ cout << 2319494 ; return 0;}
if(n==3716){ cout << 2319841 ; return 0;}
if(n==3717){ cout << 2323344 ; return 0;}
if(n==3718){ cout << 2324165 ; return 0;}
if(n==3719){ cout << 2325560 ; return 0;}
if(n==3720){ cout << 2325868 ; return 0;}
if(n==3721){ cout << 2327260 ; return 0;}
if(n==3722){ cout << 2327956 ; return 0;}
if(n==3723){ cout << 2330283 ; return 0;}
if(n==3724){ cout << 2330795 ; return 0;}
if(n==3725){ cout << 2332181 ; return 0;}
if(n==3726){ cout << 2333692 ; return 0;}
if(n==3727){ cout << 2335090 ; return 0;}
if(n==3728){ cout << 2335176 ; return 0;}
if(n==3729){ cout << 2337935 ; return 0;}
if(n==3730){ cout << 2338628 ; return 0;}
if(n==3731){ cout << 2340421 ; return 0;}
if(n==3732){ cout << 2341008 ; return 0;}
if(n==3733){ cout << 2342406 ; return 0;}
if(n==3734){ cout << 2343107 ; return 0;}
if(n==3735){ cout << 2345818 ; return 0;}
if(n==3736){ cout << 2345994 ; return 0;}
if(n==3737){ cout << 2347389 ; return 0;}
if(n==3738){ cout << 2348891 ; return 0;}
if(n==3739){ cout << 2350294 ; return 0;}
if(n==3740){ cout << 2350704 ; return 0;}
if(n==3741){ cout << 2353151 ; return 0;}
if(n==3742){ cout << 2353853 ; return 0;}
if(n==3743){ cout << 2355403 ; return 0;}
if(n==3744){ cout << 2355485 ; return 0;}
if(n==3745){ cout << 2357323 ; return 0;}
if(n==3746){ cout << 2358024 ; return 0;}
if(n==3747){ cout << 2360366 ; return 0;}
if(n==3748){ cout << 2360716 ; return 0;}
if(n==3749){ cout << 2362263 ; return 0;}
if(n==3750){ cout << 2363429 ; return 0;}
if(n==3751){ cout << 2365224 ; return 0;}
if(n==3752){ cout << 2365457 ; return 0;}
if(n==3753){ cout << 2368264 ; return 0;}
if(n==3754){ cout << 2368966 ; return 0;}
if(n==3755){ cout << 2370376 ; return 0;}
if(n==3756){ cout << 2370963 ; return 0;}
if(n==3757){ cout << 2372362 ; return 0;}
if(n==3758){ cout << 2373067 ; return 0;}
if(n==3759){ cout << 2376123 ; return 0;}
if(n==3760){ cout << 2376213 ; return 0;}
if(n==3761){ cout << 2377622 ; return 0;}
if(n==3762){ cout << 2379373 ; return 0;}
if(n==3763){ cout << 2380822 ; return 0;}
if(n==3764){ cout << 2381173 ; return 0;}
if(n==3765){ cout << 2383545 ; return 0;}
if(n==3766){ cout << 2384451 ; return 0;}
if(n==3767){ cout << 2385864 ; return 0;}
if(n==3768){ cout << 2386157 ; return 0;}
if(n==3769){ cout << 2387569 ; return 0;}
if(n==3770){ cout << 2388256 ; return 0;}
if(n==3771){ cout << 2390943 ; return 0;}
if(n==3772){ cout << 2391326 ; return 0;}
if(n==3773){ cout << 2393554 ; return 0;}
if(n==3774){ cout << 2394729 ; return 0;}
if(n==3775){ cout << 2396160 ; return 0;}
if(n==3776){ cout << 2396183 ; return 0;}
if(n==3777){ cout << 2398549 ; return 0;}
if(n==3778){ cout << 2399256 ; return 0;}
if(n==3779){ cout << 2400674 ; return 0;}
if(n==3780){ cout << 2401568 ; return 0;}
if(n==3781){ cout << 2403151 ; return 0;}
if(n==3782){ cout << 2403904 ; return 0;}
if(n==3783){ cout << 2406264 ; return 0;}
if(n==3784){ cout << 2406485 ; return 0;}
if(n==3785){ cout << 2407898 ; return 0;}
if(n==3786){ cout << 2409085 ; return 0;}
if(n==3787){ cout << 2410909 ; return 0;}
if(n==3788){ cout << 2411265 ; return 0;}
if(n==3789){ cout << 2413948 ; return 0;}
if(n==3790){ cout << 2414661 ; return 0;}
if(n==3791){ cout << 2416094 ; return 0;}
if(n==3792){ cout << 2416246 ; return 0;}
if(n==3793){ cout << 2417667 ; return 0;}
if(n==3794){ cout << 2418588 ; return 0;}
if(n==3795){ cout << 2421635 ; return 0;}
if(n==3796){ cout << 2421985 ; return 0;}
if(n==3797){ cout << 2423407 ; return 0;}
if(n==3798){ cout << 2424768 ; return 0;}
if(n==3799){ cout << 2426213 ; return 0;}
if(n==3800){ cout << 2426407 ; return 0;}
if(n==3801){ cout << 2429460 ; return 0;}
if(n==3802){ cout << 2430171 ; return 0;}
if(n==3803){ cout << 2431598 ; return 0;}
if(n==3804){ cout << 2432191 ; return 0;}
if(n==3805){ cout << 2433612 ; return 0;}
if(n==3806){ cout << 2434454 ; return 0;}
if(n==3807){ cout << 2437414 ; return 0;}
if(n==3808){ cout << 2437470 ; return 0;}
if(n==3809){ cout << 2438892 ; return 0;}
if(n==3810){ cout << 2440100 ; return 0;}
if(n==3811){ cout << 2441555 ; return 0;}
if(n==3812){ cout << 2441911 ; return 0;}
if(n==3813){ cout << 2444448 ; return 0;}
if(n==3814){ cout << 2445164 ; return 0;}
if(n==3815){ cout << 2446997 ; return 0;}
if(n==3816){ cout << 2447334 ; return 0;}
if(n==3817){ cout << 2449037 ; return 0;}
if(n==3818){ cout << 2449834 ; return 0;}
if(n==3819){ cout << 2452557 ; return 0;}
if(n==3820){ cout << 2452917 ; return 0;}
if(n==3821){ cout << 2454348 ; return 0;}
if(n==3822){ cout << 2455931 ; return 0;}
if(n==3823){ cout << 2457365 ; return 0;}
if(n==3824){ cout << 2457455 ; return 0;}
if(n==3825){ cout << 2460157 ; return 0;}
if(n==3826){ cout << 2460873 ; return 0;}
if(n==3827){ cout << 2462375 ; return 0;}
if(n==3828){ cout << 2463082 ; return 0;}
if(n==3829){ cout << 2464935 ; return 0;}
if(n==3830){ cout << 2465655 ; return 0;}
if(n==3831){ cout << 2468048 ; return 0;}
if(n==3832){ cout << 2468228 ; return 0;}
if(n==3833){ cout << 2469664 ; return 0;}
if(n==3834){ cout << 2471116 ; return 0;}
if(n==3835){ cout << 2472597 ; return 0;}
if(n==3836){ cout << 2473058 ; return 0;}
if(n==3837){ cout << 2475460 ; return 0;}
if(n==3838){ cout << 2476254 ; return 0;}
if(n==3839){ cout << 2477954 ; return 0;}
if(n==3840){ cout << 2477962 ; return 0;}
if(n==3841){ cout << 2479546 ; return 0;}
if(n==3842){ cout << 2480262 ; return 0;}
if(n==3843){ cout << 2483761 ; return 0;}
if(n==3844){ cout << 2484145 ; return 0;}
if(n==3845){ cout << 2485581 ; return 0;}
if(n==3846){ cout << 2486783 ; return 0;}
if(n==3847){ cout << 2488226 ; return 0;}
if(n==3848){ cout << 2488400 ; return 0;}
if(n==3849){ cout << 2490811 ; return 0;}
if(n==3850){ cout << 2491905 ; return 0;}
if(n==3851){ cout << 2493350 ; return 0;}
if(n==3852){ cout << 2494048 ; return 0;}
if(n==3853){ cout << 2495491 ; return 0;}
if(n==3854){ cout << 2496243 ; return 0;}
if(n==3855){ cout << 2498648 ; return 0;}
if(n==3856){ cout << 2498737 ; return 0;}
if(n==3857){ cout << 2500791 ; return 0;}
if(n==3858){ cout << 2502002 ; return 0;}
if(n==3859){ cout << 2503462 ; return 0;}
if(n==3860){ cout << 2503818 ; return 0;}
if(n==3861){ cout << 2507180 ; return 0;}
if(n==3862){ cout << 2507905 ; return 0;}
if(n==3863){ cout << 2509354 ; return 0;}
if(n==3864){ cout << 2509776 ; return 0;}
if(n==3865){ cout << 2511219 ; return 0;}
if(n==3866){ cout << 2511942 ; return 0;}
if(n==3867){ cout << 2514359 ; return 0;}
if(n==3868){ cout << 2514722 ; return 0;}
if(n==3869){ cout << 2516167 ; return 0;}
if(n==3870){ cout << 2517603 ; return 0;}
if(n==3871){ cout << 2519577 ; return 0;}
if(n==3872){ cout << 2519632 ; return 0;}
if(n==3873){ cout << 2522058 ; return 0;}
if(n==3874){ cout << 2522778 ; return 0;}
if(n==3875){ cout << 2524320 ; return 0;}
if(n==3876){ cout << 2524994 ; return 0;}
if(n==3877){ cout << 2526446 ; return 0;}
if(n==3878){ cout << 2527379 ; return 0;}
if(n==3879){ cout << 2530140 ; return 0;}
if(n==3880){ cout << 2530316 ; return 0;}
if(n==3881){ cout << 2531770 ; return 0;}
if(n==3882){ cout << 2532987 ; return 0;}
if(n==3883){ cout << 2534708 ; return 0;}
if(n==3884){ cout << 2535073 ; return 0;}
if(n==3885){ cout << 2538189 ; return 0;}
if(n==3886){ cout << 2538938 ; return 0;}
if(n==3887){ cout << 2540519 ; return 0;}
if(n==3888){ cout << 2540703 ; return 0;}
if(n==3889){ cout << 2542160 ; return 0;}
if(n==3890){ cout << 2542883 ; return 0;}
if(n==3891){ cout << 2545315 ; return 0;}
if(n==3892){ cout << 2545791 ; return 0;}
if(n==3893){ cout << 2547245 ; return 0;}
if(n==3894){ cout << 2548738 ; return 0;}
if(n==3895){ cout << 2550348 ; return 0;}
if(n==3896){ cout << 2550531 ; return 0;}
if(n==3897){ cout << 2553293 ; return 0;}
if(n==3898){ cout << 2554022 ; return 0;}
if(n==3899){ cout << 2555900 ; return 0;}
if(n==3900){ cout << 2556499 ; return 0;}
if(n==3901){ cout << 2558061 ; return 0;}
if(n==3902){ cout << 2558793 ; return 0;}
if(n==3903){ cout << 2561231 ; return 0;}
if(n==3904){ cout << 2561252 ; return 0;}
if(n==3905){ cout << 2563030 ; return 0;}
if(n==3906){ cout << 2564924 ; return 0;}
if(n==3907){ cout << 2566390 ; return 0;}
if(n==3908){ cout << 2566755 ; return 0;}
if(n==3909){ cout << 2569202 ; return 0;}
if(n==3910){ cout << 2569993 ; return 0;}
if(n==3911){ cout << 2571460 ; return 0;}
if(n==3912){ cout << 2571771 ; return 0;}
if(n==3913){ cout << 2573744 ; return 0;}
if(n==3914){ cout << 2574571 ; return 0;}
if(n==3915){ cout << 2577448 ; return 0;}
if(n==3916){ cout << 2577882 ; return 0;}
if(n==3917){ cout << 2579349 ; return 0;}
if(n==3918){ cout << 2580572 ; return 0;}
if(n==3919){ cout << 2582042 ; return 0;}
if(n==3920){ cout << 2582162 ; return 0;}
if(n==3921){ cout << 2584618 ; return 0;}
if(n==3922){ cout << 2585347 ; return 0;}
if(n==3923){ cout << 2586819 ; return 0;}
if(n==3924){ cout << 2587513 ; return 0;}
if(n==3925){ cout << 2588974 ; return 0;}
if(n==3926){ cout << 2589718 ; return 0;}
if(n==3927){ cout << 2593452 ; return 0;}
if(n==3928){ cout << 2593637 ; return 0;}
if(n==3929){ cout << 2595109 ; return 0;}
if(n==3930){ cout << 2596356 ; return 0;}
if(n==3931){ cout << 2597831 ; return 0;}
if(n==3932){ cout << 2598200 ; return 0;}
if(n==3933){ cout << 2601550 ; return 0;}
if(n==3934){ cout << 2602497 ; return 0;}
if(n==3935){ cout << 2603975 ; return 0;}
if(n==3936){ cout << 2604052 ; return 0;}
if(n==3937){ cout << 2605648 ; return 0;}
if(n==3938){ cout << 2606532 ; return 0;}
if(n==3939){ cout << 2608988 ; return 0;}
if(n==3940){ cout << 2609351 ; return 0;}
if(n==3941){ cout << 2611258 ; return 0;}
if(n==3942){ cout << 2612712 ; return 0;}
if(n==3943){ cout << 2614191 ; return 0;}
if(n==3944){ cout << 2614370 ; return 0;}
if(n==3945){ cout << 2616853 ; return 0;}
if(n==3946){ cout << 2617591 ; return 0;}
if(n==3947){ cout << 2619072 ; return 0;}
if(n==3948){ cout << 2619899 ; return 0;}
if(n==3949){ cout << 2621659 ; return 0;}
if(n==3950){ cout << 2622415 ; return 0;}
if(n==3951){ cout << 2625227 ; return 0;}
if(n==3952){ cout << 2625328 ; return 0;}
if(n==3953){ cout << 2626908 ; return 0;}
if(n==3954){ cout << 2628149 ; return 0;}
if(n==3955){ cout << 2630050 ; return 0;}
if(n==3956){ cout << 2630472 ; return 0;}
if(n==3957){ cout << 2632949 ; return 0;}
if(n==3958){ cout << 2633692 ; return 0;}
if(n==3959){ cout << 2635203 ; return 0;}
if(n==3960){ cout << 2635619 ; return 0;}
if(n==3961){ cout << 2637100 ; return 0;}
if(n==3962){ cout << 2638062 ; return 0;}
if(n==3963){ cout << 2640539 ; return 0;}
if(n==3964){ cout << 2640911 ; return 0;}
if(n==3965){ cout << 2642378 ; return 0;}
if(n==3966){ cout << 2643616 ; return 0;}
if(n==3967){ cout << 2645104 ; return 0;}
if(n==3968){ cout << 2645116 ; return 0;}
if(n==3969){ cout << 2649042 ; return 0;}
if(n==3970){ cout << 2649780 ; return 0;}
if(n==3971){ cout << 2651738 ; return 0;}
if(n==3972){ cout << 2652364 ; return 0;}
if(n==3973){ cout << 2653848 ; return 0;}
if(n==3974){ cout << 2654594 ; return 0;}
if(n==3975){ cout << 2657068 ; return 0;}
if(n==3976){ cout << 2657314 ; return 0;}
if(n==3977){ cout << 2658801 ; return 0;}
if(n==3978){ cout << 2660207 ; return 0;}
if(n==3979){ cout << 2661827 ; return 0;}
if(n==3980){ cout << 2662202 ; return 0;}
if(n==3981){ cout << 2664694 ; return 0;}
if(n==3982){ cout << 2665575 ; return 0;}
if(n==3983){ cout << 2667494 ; return 0;}
if(n==3984){ cout << 2667655 ; return 0;}
if(n==3985){ cout << 2669143 ; return 0;}
if(n==3986){ cout << 2669889 ; return 0;}
if(n==3987){ cout << 2672729 ; return 0;}
if(n==3988){ cout << 2673101 ; return 0;}
if(n==3989){ cout << 2674595 ; return 0;}
if(n==3990){ cout << 2676367 ; return 0;}
if(n==3991){ cout << 2677872 ; return 0;}
if(n==3992){ cout << 2678060 ; return 0;}
if(n==3993){ cout << 2681059 ; return 0;}
if(n==3994){ cout << 2681806 ; return 0;}
if(n==3995){ cout << 2683362 ; return 0;}
if(n==3996){ cout << 2684097 ; return 0;}
if(n==3997){ cout << 2686031 ; return 0;}
if(n==3998){ cout << 2686781 ; return 0;}
if(n==3999){ cout << 2689567 ; return 0;}
if(n==4000){ cout << 2689609 ; return 0;}
if(n==4001){ cout << 2691108 ; return 0;}
if(n==4002){ cout << 2692466 ; return 0;}
if(n==4003){ cout << 2693968 ; return 0;}
if(n==4004){ cout << 2694537 ; return 0;}
if(n==4005){ cout << 2697371 ; return 0;}
if(n==4006){ cout << 2698123 ; return 0;}
if(n==4007){ cout << 2699626 ; return 0;}
if(n==4008){ cout << 2699943 ; return 0;}
if(n==4009){ cout << 2701622 ; return 0;}
if(n==4010){ cout << 2702368 ; return 0;}
if(n==4011){ cout << 2705625 ; return 0;}
if(n==4012){ cout << 2706014 ; return 0;}
if(n==4013){ cout << 2707517 ; return 0;}
if(n==4014){ cout << 2708952 ; return 0;}
if(n==4015){ cout << 2710727 ; return 0;}
if(n==4016){ cout << 2710822 ; return 0;}
if(n==4017){ cout << 2713380 ; return 0;}
if(n==4018){ cout << 2714378 ; return 0;}
if(n==4019){ cout << 2715886 ; return 0;}
if(n==4020){ cout << 2716533 ; return 0;}
if(n==4021){ cout << 2718039 ; return 0;}
if(n==4022){ cout << 2718794 ; return 0;}
if(n==4023){ cout << 2721755 ; return 0;}
if(n==4024){ cout << 2721944 ; return 0;}
if(n==4025){ cout << 2724050 ; return 0;}
if(n==4026){ cout << 2725537 ; return 0;}
if(n==4027){ cout << 2727048 ; return 0;}
if(n==4028){ cout << 2727464 ; return 0;}
if(n==4029){ cout << 2730046 ; return 0;}
if(n==4030){ cout << 2730844 ; return 0;}
if(n==4031){ cout << 2732376 ; return 0;}
if(n==4032){ cout << 2732434 ; return 0;}
if(n==4033){ cout << 2733940 ; return 0;}
if(n==4034){ cout << 2734695 ; return 0;}
if(n==4035){ cout << 2737211 ; return 0;}
if(n==4036){ cout << 2737588 ; return 0;}
if(n==4037){ cout << 2739387 ; return 0;}
if(n==4038){ cout << 2740649 ; return 0;}
if(n==4039){ cout << 2742595 ; return 0;}
if(n==4040){ cout << 2742778 ; return 0;}
if(n==4041){ cout << 2745642 ; return 0;}
if(n==4042){ cout << 2746469 ; return 0;}
if(n==4043){ cout << 2747993 ; return 0;}
if(n==4044){ cout << 2748625 ; return 0;}
if(n==4045){ cout << 2750136 ; return 0;}
if(n==4046){ cout << 2751109 ; return 0;}
if(n==4047){ cout << 2753985 ; return 0;}
if(n==4048){ cout << 2754107 ; return 0;}
if(n==4049){ cout << 2755624 ; return 0;}
if(n==4050){ cout << 2757132 ; return 0;}
if(n==4051){ cout << 2758652 ; return 0;}
if(n==4052){ cout << 2759030 ; return 0;}
if(n==4053){ cout << 2762287 ; return 0;}
if(n==4054){ cout << 2763048 ; return 0;}
if(n==4055){ cout << 2764571 ; return 0;}
if(n==4056){ cout << 2764885 ; return 0;}
if(n==4057){ cout << 2766405 ; return 0;}
if(n==4058){ cout << 2767164 ; return 0;}
if(n==4059){ cout << 2770571 ; return 0;}
if(n==4060){ cout << 2771054 ; return 0;}
if(n==4061){ cout << 2772700 ; return 0;}
if(n==4062){ cout << 2773968 ; return 0;}
if(n==4063){ cout << 2775503 ; return 0;}
if(n==4064){ cout << 2775551 ; return 0;}
if(n==4065){ cout << 2778109 ; return 0;}
if(n==4066){ cout << 2778969 ; return 0;}
if(n==4067){ cout << 2781041 ; return 0;}
if(n==4068){ cout << 2781763 ; return 0;}
if(n==4069){ cout << 2783283 ; return 0;}
if(n==4070){ cout << 2784179 ; return 0;}
if(n==4071){ cout << 2787040 ; return 0;}
if(n==4072){ cout << 2787229 ; return 0;}
if(n==4073){ cout << 2788755 ; return 0;}
if(n==4074){ cout << 2790392 ; return 0;}
if(n==4075){ cout << 2791936 ; return 0;}
if(n==4076){ cout << 2792319 ; return 0;}
if(n==4077){ cout << 2795361 ; return 0;}
if(n==4078){ cout << 2796126 ; return 0;}
if(n==4079){ cout << 2797656 ; return 0;}
if(n==4080){ cout << 2797811 ; return 0;}
if(n==4081){ cout << 2800135 ; return 0;}
if(n==4082){ cout << 2800894 ; return 0;}
if(n==4083){ cout << 2803446 ; return 0;}
if(n==4084){ cout << 2803827 ; return 0;}
if(n==4085){ cout << 2805599 ; return 0;}
if(n==4086){ cout << 2807062 ; return 0;}
if(n==4087){ cout << 2808639 ; return 0;}
if(n==4088){ cout << 2808884 ; return 0;}
if(n==4089){ cout << 2811547 ; return 0;}
if(n==4090){ cout << 2812308 ; return 0;}
if(n==4091){ cout << 2813843 ; return 0;}
if(n==4092){ cout << 2814649 ; return 0;}
if(n==4093){ cout << 2816182 ; return 0;}
if(n==4094){ cout << 2817015 ; return 0;}
if(n==4095){ cout << 2820739 ; return 0;}
if(n==4096){ cout << 2820739 ; return 0;}
if(n==4097){ cout << 2822271 ; return 0;}
if(n==4098){ cout << 2823557 ; return 0;}
if(n==4099){ cout << 2825095 ; return 0;}
if(n==4100){ cout << 2825469 ; return 0;}
if(n==4101){ cout << 2828036 ; return 0;}
if(n==4102){ cout << 2829023 ; return 0;}
if(n==4103){ cout << 2830840 ; return 0;}
if(n==4104){ cout << 2831262 ; return 0;}
if(n==4105){ cout << 2832795 ; return 0;}
if(n==4106){ cout << 2833563 ; return 0;}
if(n==4107){ cout << 2836127 ; return 0;}
if(n==4108){ cout << 2836520 ; return 0;}
if(n==4109){ cout << 2838508 ; return 0;}
if(n==4110){ cout << 2839788 ; return 0;}
if(n==4111){ cout << 2841330 ; return 0;}
if(n==4112){ cout << 2841425 ; return 0;}
if(n==4113){ cout << 2844340 ; return 0;}
if(n==4114){ cout << 2845266 ; return 0;}
if(n==4115){ cout << 2846811 ; return 0;}
if(n==4116){ cout << 2847668 ; return 0;}
if(n==4117){ cout << 2849365 ; return 0;}
if(n==4118){ cout << 2850157 ; return 0;}
if(n==4119){ cout << 2852730 ; return 0;}
if(n==4120){ cout << 2852925 ; return 0;}
if(n==4121){ cout << 2854464 ; return 0;}
if(n==4122){ cout << 2855923 ; return 0;}
if(n==4123){ cout << 2858262 ; return 0;}
if(n==4124){ cout << 2858649 ; return 0;}
if(n==4125){ cout << 2861693 ; return 0;}
if(n==4126){ cout << 2862467 ; return 0;}
if(n==4127){ cout << 2864015 ; return 0;}
if(n==4128){ cout << 2864101 ; return 0;}
if(n==4129){ cout << 2865648 ; return 0;}
if(n==4130){ cout << 2866676 ; return 0;}
if(n==4131){ cout << 2869774 ; return 0;}
if(n==4132){ cout << 2870160 ; return 0;}
if(n==4133){ cout << 2871708 ; return 0;}
if(n==4134){ cout << 2872994 ; return 0;}
if(n==4135){ cout << 2874547 ; return 0;}
if(n==4136){ cout << 2874786 ; return 0;}
if(n==4137){ cout << 2878109 ; return 0;}
if(n==4138){ cout << 2878883 ; return 0;}
if(n==4139){ cout << 2880436 ; return 0;}
if(n==4140){ cout << 2881232 ; return 0;}
if(n==4141){ cout << 2882779 ; return 0;}
if(n==4142){ cout << 2883636 ; return 0;}
if(n==4143){ cout << 2886224 ; return 0;}
if(n==4144){ cout << 2886347 ; return 0;}
if(n==4145){ cout << 2887895 ; return 0;}
if(n==4146){ cout << 2889196 ; return 0;}
if(n==4147){ cout << 2891028 ; return 0;}
if(n==4148){ cout << 2891411 ; return 0;}
if(n==4149){ cout << 2894349 ; return 0;}
if(n==4150){ cout << 2895143 ; return 0;}
if(n==4151){ cout << 2897143 ; return 0;}
if(n==4152){ cout << 2897466 ; return 0;}
if(n==4153){ cout << 2899022 ; return 0;}
if(n==4154){ cout << 2899876 ; return 0;}
if(n==4155){ cout << 2902467 ; return 0;}
if(n==4156){ cout << 2902857 ; return 0;}
if(n==4157){ cout << 2904414 ; return 0;}
if(n==4158){ cout << 2906744 ; return 0;}
if(n==4159){ cout << 2908304 ; return 0;}
if(n==4160){ cout << 2908322 ; return 0;}
if(n==4161){ cout << 2911201 ; return 0;}
if(n==4162){ cout << 2911980 ; return 0;}
if(n==4163){ cout << 2913675 ; return 0;}
if(n==4164){ cout << 2914331 ; return 0;}
if(n==4165){ cout << 2916397 ; return 0;}
if(n==4166){ cout << 2917179 ; return 0;}
if(n==4167){ cout << 2920144 ; return 0;}
if(n==4168){ cout << 2920338 ; return 0;}
if(n==4169){ cout << 2922197 ; return 0;}
if(n==4170){ cout << 2923519 ; return 0;}
if(n==4171){ cout << 2925156 ; return 0;}
if(n==4172){ cout << 2925657 ; return 0;}
if(n==4173){ cout << 2928314 ; return 0;}
if(n==4174){ cout << 2929097 ; return 0;}
if(n==4175){ cout << 2930678 ; return 0;}
if(n==4176){ cout << 2930862 ; return 0;}
if(n==4177){ cout << 2932427 ; return 0;}
if(n==4178){ cout << 2933209 ; return 0;}
if(n==4179){ cout << 2936601 ; return 0;}
if(n==4180){ cout << 2937113 ; return 0;}
if(n==4181){ cout << 2938675 ; return 0;}
if(n==4182){ cout << 2939982 ; return 0;}
if(n==4183){ cout << 2941616 ; return 0;}
if(n==4184){ cout << 2941813 ; return 0;}
if(n==4185){ cout << 2945092 ; return 0;}
if(n==4186){ cout << 2946187 ; return 0;}
if(n==4187){ cout << 2947795 ; return 0;}
if(n==4188){ cout << 2948448 ; return 0;}
if(n==4189){ cout << 2950118 ; return 0;}
if(n==4190){ cout << 2950906 ; return 0;}
if(n==4191){ cout << 2954052 ; return 0;}
if(n==4192){ cout << 2954102 ; return 0;}
if(n==4193){ cout << 2956130 ; return 0;}
if(n==4194){ cout << 2957617 ; return 0;}
if(n==4195){ cout << 2959192 ; return 0;}
if(n==4196){ cout << 2959584 ; return 0;}
if(n==4197){ cout << 2962211 ; return 0;}
if(n==4198){ cout << 2962999 ; return 0;}
if(n==4199){ cout << 2964735 ; return 0;}
if(n==4200){ cout << 2965154 ; return 0;}
if(n==4201){ cout << 2966728 ; return 0;}
if(n==4202){ cout << 2967669 ; return 0;}
if(n==4203){ cout << 2970662 ; return 0;}
if(n==4204){ cout << 2971057 ; return 0;}
if(n==4205){ cout << 2972623 ; return 0;}
if(n==4206){ cout << 2973936 ; return 0;}
if(n==4207){ cout << 2975963 ; return 0;}
if(n==4208){ cout << 2976062 ; return 0;}
if(n==4209){ cout << 2978920 ; return 0;}
if(n==4210){ cout << 2979703 ; return 0;}
if(n==4211){ cout << 2981283 ; return 0;}
if(n==4212){ cout << 2982068 ; return 0;}
if(n==4213){ cout << 2983945 ; return 0;}
if(n==4214){ cout << 2985042 ; return 0;}
if(n==4215){ cout << 2987672 ; return 0;}
if(n==4216){ cout << 2987881 ; return 0;}
if(n==4217){ cout << 2989461 ; return 0;}
if(n==4218){ cout << 2990918 ; return 0;}
if(n==4219){ cout << 2992501 ; return 0;}
if(n==4220){ cout << 2992899 ; return 0;}
if(n==4221){ cout << 2996861 ; return 0;}
if(n==4222){ cout << 2997653 ; return 0;}
if(n==4223){ cout << 2999266 ; return 0;}
if(n==4224){ cout << 2999292 ; return 0;}
if(n==4225){ cout << 3000858 ; return 0;}
if(n==4226){ cout << 3001649 ; return 0;}
if(n==4227){ cout << 3004291 ; return 0;}
if(n==4228){ cout << 3004807 ; return 0;}
if(n==4229){ cout << 3006391 ; return 0;}
if(n==4230){ cout << 3007952 ; return 0;}
if(n==4231){ cout << 3009539 ; return 0;}
if(n==4232){ cout << 3009755 ; return 0;}
if(n==4233){ cout << 3012469 ; return 0;}
if(n==4234){ cout << 3013257 ; return 0;}
if(n==4235){ cout << 3015703 ; return 0;}
if(n==4236){ cout << 3016365 ; return 0;}
if(n==4237){ cout << 3018137 ; return 0;}
if(n==4238){ cout << 3018940 ; return 0;}
if(n==4239){ cout << 3022060 ; return 0;}
if(n==4240){ cout << 3022153 ; return 0;}
if(n==4241){ cout << 3023742 ; return 0;}
if(n==4242){ cout << 3025445 ; return 0;}
if(n==4243){ cout << 3027037 ; return 0;}
if(n==4244){ cout << 3027433 ; return 0;}
if(n==4245){ cout << 3030105 ; return 0;}
if(n==4246){ cout << 3031046 ; return 0;}
if(n==4247){ cout << 3032740 ; return 0;}
if(n==4248){ cout << 3033132 ; return 0;}
if(n==4249){ cout << 3035187 ; return 0;}
if(n==4250){ cout << 3035969 ; return 0;}
if(n==4251){ cout << 3038620 ; return 0;}
if(n==4252){ cout << 3039019 ; return 0;}
if(n==4253){ cout << 3040612 ; return 0;}
if(n==4254){ cout << 3041940 ; return 0;}
if(n==4255){ cout << 3043668 ; return 0;}
if(n==4256){ cout << 3043739 ; return 0;}
if(n==4257){ cout << 3047479 ; return 0;}
if(n==4258){ cout << 3048276 ; return 0;}
if(n==4259){ cout << 3049874 ; return 0;}
if(n==4260){ cout << 3050557 ; return 0;}
if(n==4261){ cout << 3052153 ; return 0;}
if(n==4262){ cout << 3052953 ; return 0;}
if(n==4263){ cout << 3056486 ; return 0;}
if(n==4264){ cout << 3056680 ; return 0;}
if(n==4265){ cout << 3058273 ; return 0;}
if(n==4266){ cout << 3059884 ; return 0;}
if(n==4267){ cout << 3061497 ; return 0;}
if(n==4268){ cout << 3061970 ; return 0;}
if(n==4269){ cout << 3064642 ; return 0;}
if(n==4270){ cout << 3065665 ; return 0;}
if(n==4271){ cout << 3067267 ; return 0;}
if(n==4272){ cout << 3067434 ; return 0;}
if(n==4273){ cout << 3069035 ; return 0;}
if(n==4274){ cout << 3069835 ; return 0;}
if(n==4275){ cout << 3073182 ; return 0;}
if(n==4276){ cout << 3073581 ; return 0;}
if(n==4277){ cout << 3075729 ; return 0;}
if(n==4278){ cout << 3077276 ; return 0;}
if(n==4279){ cout << 3079171 ; return 0;}
if(n==4280){ cout << 3079374 ; return 0;}
if(n==4281){ cout << 3082055 ; return 0;}
if(n==4282){ cout << 3082856 ; return 0;}
if(n==4283){ cout << 3084463 ; return 0;}
if(n==4284){ cout << 3085440 ; return 0;}
if(n==4285){ cout << 3087041 ; return 0;}
if(n==4286){ cout << 3087845 ; return 0;}
if(n==4287){ cout << 3090523 ; return 0;}
if(n==4288){ cout << 3090549 ; return 0;}
if(n==4289){ cout << 3092156 ; return 0;}
if(n==4290){ cout << 3093736 ; return 0;}
if(n==4291){ cout << 3095803 ; return 0;}
if(n==4292){ cout << 3096199 ; return 0;}
if(n==4293){ cout << 3099399 ; return 0;}
if(n==4294){ cout << 3100289 ; return 0;}
if(n==4295){ cout << 3101902 ; return 0;}
if(n==4296){ cout << 3102243 ; return 0;}
if(n==4297){ cout << 3103853 ; return 0;}
if(n==4298){ cout << 3104896 ; return 0;}
if(n==4299){ cout << 3107583 ; return 0;}
if(n==4300){ cout << 3108002 ; return 0;}
if(n==4301){ cout << 3110074 ; return 0;}
if(n==4302){ cout << 3111611 ; return 0;}
if(n==4303){ cout << 3113233 ; return 0;}
if(n==4304){ cout << 3113332 ; return 0;}
if(n==4305){ cout << 3116787 ; return 0;}
if(n==4306){ cout << 3117593 ; return 0;}
if(n==4307){ cout << 3119263 ; return 0;}
if(n==4308){ cout << 3119940 ; return 0;}
if(n==4309){ cout << 3121685 ; return 0;}
if(n==4310){ cout << 3122495 ; return 0;}
if(n==4311){ cout << 3125562 ; return 0;}
if(n==4312){ cout << 3125879 ; return 0;}
if(n==4313){ cout << 3127684 ; return 0;}
if(n==4314){ cout << 3129036 ; return 0;}
if(n==4315){ cout << 3130656 ; return 0;}
if(n==4316){ cout << 3131069 ; return 0;}
if(n==4317){ cout << 3133771 ; return 0;}
if(n==4318){ cout << 3134592 ; return 0;}
if(n==4319){ cout << 3136673 ; return 0;}
if(n==4320){ cout << 3136772 ; return 0;}
if(n==4321){ cout << 3138386 ; return 0;}
if(n==4322){ cout << 3139195 ; return 0;}
if(n==4323){ cout << 3142443 ; return 0;}
if(n==4324){ cout << 3142902 ; return 0;}
if(n==4325){ cout << 3144513 ; return 0;}
if(n==4326){ cout << 3146285 ; return 0;}
if(n==4327){ cout << 3147908 ; return 0;}
if(n==4328){ cout << 3148109 ; return 0;}
if(n==4329){ cout << 3151170 ; return 0;}
if(n==4330){ cout << 3151976 ; return 0;}
if(n==4331){ cout << 3153644 ; return 0;}
if(n==4332){ cout << 3154399 ; return 0;}
if(n==4333){ cout << 3156495 ; return 0;}
if(n==4334){ cout << 3157454 ; return 0;}
if(n==4335){ cout << 3160156 ; return 0;}
if(n==4336){ cout << 3160258 ; return 0;}
if(n==4337){ cout << 3161883 ; return 0;}
if(n==4338){ cout << 3163421 ; return 0;}
if(n==4339){ cout << 3165049 ; return 0;}
if(n==4340){ cout << 3165604 ; return 0;}
if(n==4341){ cout << 3168321 ; return 0;}
if(n==4342){ cout << 3169143 ; return 0;}
if(n==4343){ cout << 3170846 ; return 0;}
if(n==4344){ cout << 3171184 ; return 0;}
if(n==4345){ cout << 3173157 ; return 0;}
if(n==4346){ cout << 3173966 ; return 0;}
if(n==4347){ cout << 3178439 ; return 0;}
if(n==4348){ cout << 3178847 ; return 0;}
if(n==4349){ cout << 3180476 ; return 0;}
if(n==4350){ cout << 3181825 ; return 0;}
if(n==4351){ cout << 3183627 ; return 0;}
if(n==4352){ cout << 3183632 ; return 0;}
if(n==4353){ cout << 3186358 ; return 0;}
if(n==4354){ cout << 3187414 ; return 0;}
if(n==4355){ cout << 3189090 ; return 0;}
if(n==4356){ cout << 3190020 ; return 0;}
if(n==4357){ cout << 3191652 ; return 0;}
if(n==4358){ cout << 3192470 ; return 0;}
if(n==4359){ cout << 3195193 ; return 0;}
if(n==4360){ cout << 3195391 ; return 0;}
if(n==4361){ cout << 3197559 ; return 0;}
if(n==4362){ cout << 3198926 ; return 0;}
if(n==4363){ cout << 3200563 ; return 0;}
if(n==4364){ cout << 3200973 ; return 0;}
if(n==4365){ cout << 3204062 ; return 0;}
if(n==4366){ cout << 3204907 ; return 0;}
if(n==4367){ cout << 3206841 ; return 0;}
if(n==4368){ cout << 3207059 ; return 0;}
if(n==4369){ cout << 3208693 ; return 0;}
if(n==4370){ cout << 3209676 ; return 0;}
if(n==4371){ cout << 3212708 ; return 0;}
if(n==4372){ cout << 3213116 ; return 0;}
if(n==4373){ cout << 3214754 ; return 0;}
if(n==4374){ cout << 3216397 ; return 0;}
if(n==4375){ cout << 3218500 ; return 0;}
if(n==4376){ cout << 3218706 ; return 0;}
if(n==4377){ cout << 3221447 ; return 0;}
if(n==4378){ cout << 3222427 ; return 0;}
if(n==4379){ cout << 3224089 ; return 0;}
if(n==4380){ cout << 3224769 ; return 0;}
if(n==4381){ cout << 3226406 ; return 0;}
if(n==4382){ cout << 3227461 ; return 0;}
if(n==4383){ cout << 3230579 ; return 0;}
if(n==4384){ cout << 3230629 ; return 0;}
if(n==4385){ cout << 3232267 ; return 0;}
if(n==4386){ cout << 3233706 ; return 0;}
if(n==4387){ cout << 3235382 ; return 0;}
if(n==4388){ cout << 3235792 ; return 0;}
if(n==4389){ cout << 3240405 ; return 0;}
if(n==4390){ cout << 3241230 ; return 0;}
if(n==4391){ cout << 3242877 ; return 0;}
if(n==4392){ cout << 3243265 ; return 0;}
if(n==4393){ cout << 3245074 ; return 0;}
if(n==4394){ cout << 3245893 ; return 0;}
if(n==4395){ cout << 3248634 ; return 0;}
if(n==4396){ cout << 3249162 ; return 0;}
if(n==4397){ cout << 3250809 ; return 0;}
if(n==4398){ cout << 3252182 ; return 0;}
if(n==4399){ cout << 3253870 ; return 0;}
if(n==4400){ cout << 3253989 ; return 0;}
if(n==4401){ cout << 3257273 ; return 0;}
if(n==4402){ cout << 3258176 ; return 0;}
if(n==4403){ cout << 3260293 ; return 0;}
if(n==4404){ cout << 3260985 ; return 0;}
if(n==4405){ cout << 3262631 ; return 0;}
if(n==4406){ cout << 3263458 ; return 0;}
if(n==4407){ cout << 3266208 ; return 0;}
if(n==4408){ cout << 3266435 ; return 0;}
if(n==4409){ cout << 3268087 ; return 0;}
if(n==4410){ cout << 3270158 ; return 0;}
if(n==4411){ cout << 3272113 ; return 0;}
if(n==4412){ cout << 3272527 ; return 0;}
if(n==4413){ cout << 3275289 ; return 0;}
if(n==4414){ cout << 3276117 ; return 0;}
if(n==4415){ cout << 3277775 ; return 0;}
if(n==4416){ cout << 3277822 ; return 0;}
if(n==4417){ cout << 3279958 ; return 0;}
if(n==4418){ cout << 3280822 ; return 0;}
if(n==4419){ cout << 3283968 ; return 0;}
if(n==4420){ cout << 3284363 ; return 0;}
if(n==4421){ cout << 3286019 ; return 0;}
if(n==4422){ cout << 3287707 ; return 0;}
if(n==4423){ cout << 3289366 ; return 0;}
if(n==4424){ cout << 3289639 ; return 0;}
if(n==4425){ cout << 3292497 ; return 0;}
if(n==4426){ cout << 3293325 ; return 0;}
if(n==4427){ cout << 3295160 ; return 0;}
if(n==4428){ cout << 3295978 ; return 0;}
if(n==4429){ cout << 3297750 ; return 0;}
if(n==4430){ cout << 3298583 ; return 0;}
if(n==4431){ cout << 3302179 ; return 0;}
if(n==4432){ cout << 3302281 ; return 0;}
if(n==4433){ cout << 3304371 ; return 0;}
if(n==4434){ cout << 3305762 ; return 0;}
if(n==4435){ cout << 3307427 ; return 0;}
if(n==4436){ cout << 3307841 ; return 0;}
if(n==4437){ cout << 3310981 ; return 0;}
if(n==4438){ cout << 3312049 ; return 0;}
if(n==4439){ cout << 3313857 ; return 0;}
if(n==4440){ cout << 3314198 ; return 0;}
if(n==4441){ cout << 3315862 ; return 0;}
if(n==4442){ cout << 3316693 ; return 0;}
if(n==4443){ cout << 3319470 ; return 0;}
if(n==4444){ cout << 3319961 ; return 0;}
if(n==4445){ cout << 3322136 ; return 0;}
if(n==4446){ cout << 3323878 ; return 0;}
if(n==4447){ cout << 3325546 ; return 0;}
if(n==4448){ cout << 3325599 ; return 0;}
if(n==4449){ cout << 3328385 ; return 0;}
if(n==4450){ cout << 3329209 ; return 0;}
if(n==4451){ cout << 3330879 ; return 0;}
if(n==4452){ cout << 3331772 ; return 0;}
if(n==4453){ cout << 3333436 ; return 0;}
if(n==4454){ cout << 3334284 ; return 0;}
if(n==4455){ cout << 3338213 ; return 0;}
if(n==4456){ cout << 3338420 ; return 0;}
if(n==4457){ cout << 3340090 ; return 0;}
if(n==4458){ cout << 3341487 ; return 0;}
if(n==4459){ cout << 3343713 ; return 0;}
if(n==4460){ cout << 3344133 ; return 0;}
if(n==4461){ cout << 3346925 ; return 0;}
if(n==4462){ cout << 3347833 ; return 0;}
if(n==4463){ cout << 3349507 ; return 0;}
if(n==4464){ cout << 3349718 ; return 0;}
if(n==4465){ cout << 3351646 ; return 0;}
if(n==4466){ cout << 3352917 ; return 0;}
if(n==4467){ cout << 3355709 ; return 0;}
if(n==4468){ cout << 3356126 ; return 0;}
if(n==4469){ cout << 3357796 ; return 0;}
if(n==4470){ cout << 3359187 ; return 0;}
if(n==4471){ cout << 3360875 ; return 0;}
if(n==4472){ cout << 3361093 ; return 0;}
if(n==4473){ cout << 3365282 ; return 0;}
if(n==4474){ cout << 3366119 ; return 0;}
if(n==4475){ cout << 3367813 ; return 0;}
if(n==4476){ cout << 3368511 ; return 0;}
if(n==4477){ cout << 3370522 ; return 0;}
if(n==4478){ cout << 3371362 ; return 0;}
if(n==4479){ cout << 3374160 ; return 0;}
if(n==4480){ cout << 3374175 ; return 0;}
if(n==4481){ cout << 3375854 ; return 0;}
if(n==4482){ cout << 3377548 ; return 0;}
if(n==4483){ cout << 3379230 ; return 0;}
if(n==4484){ cout << 3379712 ; return 0;}
if(n==4485){ cout << 3382753 ; return 0;}
if(n==4486){ cout << 3383595 ; return 0;}
if(n==4487){ cout << 3385757 ; return 0;}
if(n==4488){ cout << 3386176 ; return 0;}
if(n==4489){ cout << 3387911 ; return 0;}
if(n==4490){ cout << 3388747 ; return 0;}
if(n==4491){ cout << 3391944 ; return 0;}
if(n==4492){ cout << 3392366 ; return 0;}
if(n==4493){ cout << 3394049 ; return 0;}
if(n==4494){ cout << 3395890 ; return 0;}
if(n==4495){ cout << 3397678 ; return 0;}
if(n==4496){ cout << 3397782 ; return 0;}
if(n==4497){ cout << 3400598 ; return 0;}
if(n==4498){ cout << 3401435 ; return 0;}
if(n==4499){ cout << 3403429 ; return 0;}
if(n==4500){ cout << 3404222 ; return 0;}
if(n==4501){ cout << 3406399 ; return 0;}
if(n==4502){ cout << 3407244 ; return 0;}
if(n==4503){ cout << 3410435 ; return 0;}
if(n==4504){ cout << 3410647 ; return 0;}
if(n==4505){ cout << 3412317 ; return 0;}
if(n==4506){ cout << 3413729 ; return 0;}
if(n==4507){ cout << 3415420 ; return 0;}
if(n==4508){ cout << 3416029 ; return 0;}
if(n==4509){ cout << 3419389 ; return 0;}
if(n==4510){ cout << 3420384 ; return 0;}
if(n==4511){ cout << 3422084 ; return 0;}
if(n==4512){ cout << 3422176 ; return 0;}
if(n==4513){ cout << 3423867 ; return 0;}
if(n==4514){ cout << 3424707 ; return 0;}
if(n==4515){ cout << 3428504 ; return 0;}
if(n==4516){ cout << 3428926 ; return 0;}
if(n==4517){ cout << 3430618 ; return 0;}
if(n==4518){ cout << 3432234 ; return 0;}
if(n==4519){ cout << 3433929 ; return 0;}
if(n==4520){ cout << 3434135 ; return 0;}
if(n==4521){ cout << 3437479 ; return 0;}
if(n==4522){ cout << 3438684 ; return 0;}
if(n==4523){ cout << 3440381 ; return 0;}
if(n==4524){ cout << 3441082 ; return 0;}
if(n==4525){ cout << 3442768 ; return 0;}
if(n==4526){ cout << 3443670 ; return 0;}
if(n==4527){ cout << 3446890 ; return 0;}
if(n==4528){ cout << 3446997 ; return 0;}
if(n==4529){ cout << 3449187 ; return 0;}
if(n==4530){ cout << 3450620 ; return 0;}
if(n==4531){ cout << 3452465 ; return 0;}
if(n==4532){ cout << 3452977 ; return 0;}
if(n==4533){ cout << 3455814 ; return 0;}
if(n==4534){ cout << 3456665 ; return 0;}
if(n==4535){ cout << 3458368 ; return 0;}
if(n==4536){ cout << 3458913 ; return 0;}
if(n==4537){ cout << 3460608 ; return 0;}
if(n==4538){ cout << 3461457 ; return 0;}
if(n==4539){ cout << 3464294 ; return 0;}
if(n==4540){ cout << 3464722 ; return 0;}
if(n==4541){ cout << 3466620 ; return 0;}
if(n==4542){ cout << 3468038 ; return 0;}
if(n==4543){ cout << 3470716 ; return 0;}
if(n==4544){ cout << 3470743 ; return 0;}
if(n==4545){ cout << 3473957 ; return 0;}
if(n==4546){ cout << 3474808 ; return 0;}
if(n==4547){ cout << 3476514 ; return 0;}
if(n==4548){ cout << 3477230 ; return 0;}
if(n==4549){ cout << 3478934 ; return 0;}
if(n==4550){ cout << 3480020 ; return 0;}
if(n==4551){ cout << 3482860 ; return 0;}
if(n==4552){ cout << 3483072 ; return 0;}
if(n==4553){ cout << 3484773 ; return 0;}
if(n==4554){ cout << 3486848 ; return 0;}
if(n==4555){ cout << 3488558 ; return 0;}
if(n==4556){ cout << 3488998 ; return 0;}
if(n==4557){ cout << 3493020 ; return 0;}
if(n==4558){ cout << 3493913 ; return 0;}
if(n==4559){ cout << 3495694 ; return 0;}
if(n==4560){ cout << 3495891 ; return 0;}
if(n==4561){ cout << 3497600 ; return 0;}
if(n==4562){ cout << 3498454 ; return 0;}
if(n==4563){ cout << 3501811 ; return 0;}
if(n==4564){ cout << 3502368 ; return 0;}
if(n==4565){ cout << 3504440 ; return 0;}
if(n==4566){ cout << 3505867 ; return 0;}
if(n==4567){ cout << 3507580 ; return 0;}
if(n==4568){ cout << 3507795 ; return 0;}
if(n==4569){ cout << 3510656 ; return 0;}
if(n==4570){ cout << 3511507 ; return 0;}
if(n==4571){ cout << 3513709 ; return 0;}
if(n==4572){ cout << 3514532 ; return 0;}
if(n==4573){ cout << 3516241 ; return 0;}
if(n==4574){ cout << 3517099 ; return 0;}
if(n==4575){ cout << 3519948 ; return 0;}
if(n==4576){ cout << 3520010 ; return 0;}
if(n==4577){ cout << 3521894 ; return 0;}
if(n==4578){ cout << 3523732 ; return 0;}
if(n==4579){ cout << 3525630 ; return 0;}
if(n==4580){ cout << 3526053 ; return 0;}
if(n==4581){ cout << 3529297 ; return 0;}
if(n==4582){ cout << 3530176 ; return 0;}
if(n==4583){ cout << 3531895 ; return 0;}
if(n==4584){ cout << 3532257 ; return 0;}
if(n==4585){ cout << 3534500 ; return 0;}
if(n==4586){ cout << 3535358 ; return 0;}
if(n==4587){ cout << 3538801 ; return 0;}
if(n==4588){ cout << 3539257 ; return 0;}
if(n==4589){ cout << 3540972 ; return 0;}
if(n==4590){ cout << 3542660 ; return 0;}
if(n==4591){ cout << 3544382 ; return 0;}
if(n==4592){ cout << 3544519 ; return 0;}
if(n==4593){ cout << 3547395 ; return 0;}
if(n==4594){ cout << 3548255 ; return 0;}
if(n==4595){ cout << 3549980 ; return 0;}
if(n==4596){ cout << 3550702 ; return 0;}
if(n==4597){ cout << 3552424 ; return 0;}
if(n==4598){ cout << 3553569 ; return 0;}
if(n==4599){ cout << 3557759 ; return 0;}
if(n==4600){ cout << 3557990 ; return 0;}
if(n==4601){ cout << 3559831 ; return 0;}
if(n==4602){ cout << 3561318 ; return 0;}
if(n==4603){ cout << 3563045 ; return 0;}
if(n==4604){ cout << 3563477 ; return 0;}
if(n==4605){ cout << 3566374 ; return 0;}
if(n==4606){ cout << 3567568 ; return 0;}
if(n==4607){ cout << 3569307 ; return 0;}
if(n==4608){ cout << 3569314 ; return 0;}
if(n==4609){ cout << 3571368 ; return 0;}
if(n==4610){ cout << 3572226 ; return 0;}
if(n==4611){ cout << 3575102 ; return 0;}
if(n==4612){ cout << 3575533 ; return 0;}
if(n==4613){ cout << 3577764 ; return 0;}
if(n==4614){ cout << 3579206 ; return 0;}
if(n==4615){ cout << 3580979 ; return 0;}
if(n==4616){ cout << 3581194 ; return 0;}
if(n==4617){ cout << 3585021 ; return 0;}
if(n==4618){ cout << 3585885 ; return 0;}
if(n==4619){ cout << 3587727 ; return 0;}
if(n==4620){ cout << 3588824 ; return 0;}
if(n==4621){ cout << 3590555 ; return 0;}
if(n==4622){ cout << 3591422 ; return 0;}
if(n==4623){ cout << 3594658 ; return 0;}
if(n==4624){ cout << 3594764 ; return 0;}
if(n==4625){ cout << 3596483 ; return 0;}
if(n==4626){ cout << 3598123 ; return 0;}
if(n==4627){ cout << 3600352 ; return 0;}
if(n==4628){ cout << 3600780 ; return 0;}
if(n==4629){ cout << 3603677 ; return 0;}
if(n==4630){ cout << 3604547 ; return 0;}
if(n==4631){ cout << 3606598 ; return 0;}
if(n==4632){ cout << 3606960 ; return 0;}
if(n==4633){ cout << 3608693 ; return 0;}
if(n==4634){ cout << 3609817 ; return 0;}
if(n==4635){ cout << 3613163 ; return 0;}
if(n==4636){ cout << 3613642 ; return 0;}
if(n==4637){ cout << 3615379 ; return 0;}
if(n==4638){ cout << 3616827 ; return 0;}
if(n==4639){ cout << 3618567 ; return 0;}
if(n==4640){ cout << 3618615 ; return 0;}
if(n==4641){ cout << 3622340 ; return 0;}
if(n==4642){ cout << 3623380 ; return 0;}
if(n==4643){ cout << 3625122 ; return 0;}
if(n==4644){ cout << 3626021 ; return 0;}
if(n==4645){ cout << 3627757 ; return 0;}
if(n==4646){ cout << 3628702 ; return 0;}
if(n==4647){ cout << 3631605 ; return 0;}
if(n==4648){ cout << 3631892 ; return 0;}
if(n==4649){ cout << 3633634 ; return 0;}
if(n==4650){ cout << 3635178 ; return 0;}
if(n==4651){ cout << 3636923 ; return 0;}
if(n==4652){ cout << 3637360 ; return 0;}
if(n==4653){ cout << 3641424 ; return 0;}
if(n==4654){ cout << 3642305 ; return 0;}
if(n==4655){ cout << 3644863 ; return 0;}
if(n==4656){ cout << 3645045 ; return 0;}
if(n==4657){ cout << 3646790 ; return 0;}
if(n==4658){ cout << 3647659 ; return 0;}
if(n==4659){ cout << 3650571 ; return 0;}
if(n==4660){ cout << 3651002 ; return 0;}
if(n==4661){ cout << 3652855 ; return 0;}
if(n==4662){ cout << 3654977 ; return 0;}
if(n==4663){ cout << 3656726 ; return 0;}
if(n==4664){ cout << 3656983 ; return 0;}
if(n==4665){ cout << 3659916 ; return 0;}
if(n==4666){ cout << 3660789 ; return 0;}
if(n==4667){ cout << 3662547 ; return 0;}
if(n==4668){ cout << 3663275 ; return 0;}
if(n==4669){ cout << 3665720 ; return 0;}
if(n==4670){ cout << 3666598 ; return 0;}
if(n==4671){ cout << 3670036 ; return 0;}
if(n==4672){ cout << 3670062 ; return 0;}
if(n==4673){ cout << 3671813 ; return 0;}
if(n==4674){ cout << 3673432 ; return 0;}
if(n==4675){ cout << 3675495 ; return 0;}
if(n==4676){ cout << 3676065 ; return 0;}
if(n==4677){ cout << 3678992 ; return 0;}
if(n==4678){ cout << 3679870 ; return 0;}
if(n==4679){ cout << 3681625 ; return 0;}
if(n==4680){ cout << 3682034 ; return 0;}
if(n==4681){ cout << 3683927 ; return 0;}
if(n==4682){ cout << 3684803 ; return 0;}
if(n==4683){ cout << 3688600 ; return 0;}
if(n==4684){ cout << 3689040 ; return 0;}
if(n==4685){ cout << 3690791 ; return 0;}
if(n==4686){ cout << 3692572 ; return 0;}
if(n==4687){ cout << 3694410 ; return 0;}
if(n==4688){ cout << 3694518 ; return 0;}
if(n==4689){ cout << 3697841 ; return 0;}
if(n==4690){ cout << 3699004 ; return 0;}
if(n==4691){ cout << 3700764 ; return 0;}
if(n==4692){ cout << 3701561 ; return 0;}
if(n==4693){ cout << 3703515 ; return 0;}
if(n==4694){ cout << 3704396 ; return 0;}
if(n==4695){ cout << 3707326 ; return 0;}
if(n==4696){ cout << 3707547 ; return 0;}
if(n==4697){ cout << 3710222 ; return 0;}
if(n==4698){ cout << 3711973 ; return 0;}
if(n==4699){ cout << 3713761 ; return 0;}
if(n==4700){ cout << 3714217 ; return 0;}
if(n==4701){ cout << 3717159 ; return 0;}
if(n==4702){ cout << 3718041 ; return 0;}
if(n==4703){ cout << 3719805 ; return 0;}
if(n==4704){ cout << 3719927 ; return 0;}
if(n==4705){ cout << 3721685 ; return 0;}
if(n==4706){ cout << 3722561 ; return 0;}
if(n==4707){ cout << 3725911 ; return 0;}
if(n==4708){ cout << 3726444 ; return 0;}
if(n==4709){ cout << 3728204 ; return 0;}
if(n==4710){ cout << 3729670 ; return 0;}
if(n==4711){ cout << 3731940 ; return 0;}
if(n==4712){ cout << 3732200 ; return 0;}
if(n==4713){ cout << 3735151 ; return 0;}
if(n==4714){ cout << 3736033 ; return 0;}
if(n==4715){ cout << 3737949 ; return 0;}
if(n==4716){ cout << 3738800 ; return 0;}
if(n==4717){ cout << 3740563 ; return 0;}
if(n==4718){ cout << 3741699 ; return 0;}
if(n==4719){ cout << 3745235 ; return 0;}
if(n==4720){ cout << 3745348 ; return 0;}
if(n==4721){ cout << 3747117 ; return 0;}
if(n==4722){ cout << 3748598 ; return 0;}
if(n==4723){ cout << 3750370 ; return 0;}
if(n==4724){ cout << 3750811 ; return 0;}
if(n==4725){ cout << 3755281 ; return 0;}
if(n==4726){ cout << 3756180 ; return 0;}
if(n==4727){ cout << 3757973 ; return 0;}
if(n==4728){ cout << 3758341 ; return 0;}
if(n==4729){ cout << 3760113 ; return 0;}
if(n==4730){ cout << 3761210 ; return 0;}
if(n==4731){ cout << 3764563 ; return 0;}
if(n==4732){ cout << 3765130 ; return 0;}
if(n==4733){ cout << 3766903 ; return 0;}
if(n==4734){ cout << 3768593 ; return 0;}
if(n==4735){ cout << 3770371 ; return 0;}
if(n==4736){ cout << 3770383 ; return 0;}
if(n==4737){ cout << 3773349 ; return 0;}
if(n==4738){ cout << 3774333 ; return 0;}
if(n==4739){ cout << 3776616 ; return 0;}
if(n==4740){ cout << 3777374 ; return 0;}
if(n==4741){ cout << 3779485 ; return 0;}
if(n==4742){ cout << 3780375 ; return 0;}
if(n==4743){ cout << 3783953 ; return 0;}
if(n==4744){ cout << 3784174 ; return 0;}
if(n==4745){ cout << 3785934 ; return 0;}
if(n==4746){ cout << 3787841 ; return 0;}
if(n==4747){ cout << 3789695 ; return 0;}
if(n==4748){ cout << 3790141 ; return 0;}
if(n==4749){ cout << 3793113 ; return 0;}
if(n==4750){ cout << 3794093 ; return 0;}
if(n==4751){ cout << 3795875 ; return 0;}
if(n==4752){ cout << 3796138 ; return 0;}
if(n==4753){ cout << 3798501 ; return 0;}
if(n==4754){ cout << 3799391 ; return 0;}
if(n==4755){ cout << 3802357 ; return 0;}
if(n==4756){ cout << 3802797 ; return 0;}
if(n==4757){ cout << 3804686 ; return 0;}
if(n==4758){ cout << 3806167 ; return 0;}
if(n==4759){ cout << 3807952 ; return 0;}
if(n==4760){ cout << 3808233 ; return 0;}
if(n==4761){ cout << 3811912 ; return 0;}
if(n==4762){ cout << 3812803 ; return 0;}
if(n==4763){ cout << 3814914 ; return 0;}
if(n==4764){ cout << 3815657 ; return 0;}
if(n==4765){ cout << 3817438 ; return 0;}
if(n==4766){ cout << 3818332 ; return 0;}
if(n==4767){ cout << 3822198 ; return 0;}
if(n==4768){ cout << 3822252 ; return 0;}
if(n==4769){ cout << 3824246 ; return 0;}
if(n==4770){ cout << 3825930 ; return 0;}
if(n==4771){ cout << 3827727 ; return 0;}
if(n==4772){ cout << 3828173 ; return 0;}
if(n==4773){ cout << 3831295 ; return 0;}
if(n==4774){ cout << 3832743 ; return 0;}
if(n==4775){ cout << 3834549 ; return 0;}
if(n==4776){ cout << 3834926 ; return 0;}
if(n==4777){ cout << 3836713 ; return 0;}
if(n==4778){ cout << 3837607 ; return 0;}
if(n==4779){ cout << 3841296 ; return 0;}
if(n==4780){ cout << 3841746 ; return 0;}
if(n==4781){ cout << 3844058 ; return 0;}
if(n==4782){ cout << 3845551 ; return 0;}
if(n==4783){ cout << 3847345 ; return 0;}
if(n==4784){ cout << 3847465 ; return 0;}
if(n==4785){ cout << 3850995 ; return 0;}
if(n==4786){ cout << 3851891 ; return 0;}
if(n==4787){ cout << 3853687 ; return 0;}
if(n==4788){ cout << 3854895 ; return 0;}
if(n==4789){ cout << 3856689 ; return 0;}
if(n==4790){ cout << 3857589 ; return 0;}
if(n==4791){ cout << 3860582 ; return 0;}
if(n==4792){ cout << 3860807 ; return 0;}
if(n==4793){ cout << 3862603 ; return 0;}
if(n==4794){ cout << 3864165 ; return 0;}
if(n==4795){ cout << 3866471 ; return 0;}
if(n==4796){ cout << 3867001 ; return 0;}
if(n==4797){ cout << 3870396 ; return 0;}
if(n==4798){ cout << 3871296 ; return 0;}
if(n==4799){ cout << 3873096 ; return 0;}
if(n==4800){ cout << 3873140 ; return 0;}
if(n==4801){ cout << 3874939 ; return 0;}
if(n==4802){ cout << 3876139 ; return 0;}
if(n==4803){ cout << 3879141 ; return 0;}
if(n==4804){ cout << 3879590 ; return 0;}
if(n==4805){ cout << 3881510 ; return 0;}
if(n==4806){ cout << 3883282 ; return 0;}
if(n==4807){ cout << 3885843 ; return 0;}
if(n==4808){ cout << 3886067 ; return 0;}
if(n==4809){ cout << 3889930 ; return 0;}
if(n==4810){ cout << 3890812 ; return 0;}
if(n==4811){ cout << 3892629 ; return 0;}
if(n==4812){ cout << 3893381 ; return 0;}
if(n==4813){ cout << 3895184 ; return 0;}
if(n==4814){ cout << 3896107 ; return 0;}
if(n==4815){ cout << 3899583 ; return 0;}
if(n==4816){ cout << 3899735 ; return 0;}
if(n==4817){ cout << 3901540 ; return 0;}
if(n==4818){ cout << 3903324 ; return 0;}
if(n==4819){ cout << 3905175 ; return 0;}
if(n==4820){ cout << 3905621 ; return 0;}
if(n==4821){ cout << 3908638 ; return 0;}
if(n==4822){ cout << 3909543 ; return 0;}
if(n==4823){ cout << 3911862 ; return 0;}
if(n==4824){ cout << 3912305 ; return 0;}
if(n==4825){ cout << 3914104 ; return 0;}
if(n==4826){ cout << 3915120 ; return 0;}
if(n==4827){ cout << 3918137 ; return 0;}
if(n==4828){ cout << 3918601 ; return 0;}
if(n==4829){ cout << 3920751 ; return 0;}
if(n==4830){ cout << 3922859 ; return 0;}
if(n==4831){ cout << 3924671 ; return 0;}
if(n==4832){ cout << 3924728 ; return 0;}
if(n==4833){ cout << 3928330 ; return 0;}
if(n==4834){ cout << 3929235 ; return 0;}
if(n==4835){ cout << 3931050 ; return 0;}
if(n==4836){ cout << 3931853 ; return 0;}
if(n==4837){ cout << 3934192 ; return 0;}
if(n==4838){ cout << 3935130 ; return 0;}
if(n==4839){ cout << 3938153 ; return 0;}
if(n==4840){ cout << 3938424 ; return 0;}
if(n==4841){ cout << 3940353 ; return 0;}
if(n==4842){ cout << 3942067 ; return 0;}
if(n==4843){ cout << 3943903 ; return 0;}
if(n==4844){ cout << 3944485 ; return 0;}
if(n==4845){ cout << 3947832 ; return 0;}
if(n==4846){ cout << 3948741 ; return 0;}
if(n==4847){ cout << 3950585 ; return 0;}
if(n==4848){ cout << 3950773 ; return 0;}
if(n==4849){ cout << 3952585 ; return 0;}
if(n==4850){ cout << 3953484 ; return 0;}
if(n==4851){ cout << 3958874 ; return 0;}
if(n==4852){ cout << 3959327 ; return 0;}
if(n==4853){ cout << 3961324 ; return 0;}
if(n==4854){ cout << 3962841 ; return 0;}
if(n==4855){ cout << 3964664 ; return 0;}
if(n==4856){ cout << 3964892 ; return 0;}
if(n==4857){ cout << 3967933 ; return 0;}
if(n==4858){ cout << 3969111 ; return 0;}
if(n==4859){ cout << 3971018 ; return 0;}
if(n==4860){ cout << 3971928 ; return 0;}
if(n==4861){ cout << 3973749 ; return 0;}
if(n==4862){ cout << 3974822 ; return 0;}
if(n==4863){ cout << 3977860 ; return 0;}
if(n==4864){ cout << 3977868 ; return 0;}
if(n==4865){ cout << 3980246 ; return 0;}
if(n==4866){ cout << 3981772 ; return 0;}
if(n==4867){ cout << 3983713 ; return 0;}
if(n==4868){ cout << 3984168 ; return 0;}
if(n==4869){ cout << 3987616 ; return 0;}
if(n==4870){ cout << 3988531 ; return 0;}
if(n==4871){ cout << 3990358 ; return 0;}
if(n==4872){ cout << 3990846 ; return 0;}
if(n==4873){ cout << 3993017 ; return 0;}
if(n==4874){ cout << 3993929 ; return 0;}
if(n==4875){ cout << 3996961 ; return 0;}
if(n==4876){ cout << 3997456 ; return 0;}
if(n==4877){ cout << 3999283 ; return 0;}
if(n==4878){ cout << 4001024 ; return 0;}
if(n==4879){ cout << 4003372 ; return 0;}
if(n==4880){ cout << 4003480 ; return 0;}
if(n==4881){ cout << 4006536 ; return 0;}
if(n==4882){ cout << 4007450 ; return 0;}
if(n==4883){ cout << 4009474 ; return 0;}
if(n==4884){ cout << 4010376 ; return 0;}
if(n==4885){ cout << 4012202 ; return 0;}
if(n==4886){ cout << 4013378 ; return 0;}
if(n==4887){ cout << 4016975 ; return 0;}
if(n==4888){ cout << 4017212 ; return 0;}
if(n==4889){ cout << 4019044 ; return 0;}
if(n==4890){ cout << 4020591 ; return 0;}
if(n==4891){ cout << 4022480 ; return 0;}
if(n==4892){ cout << 4022939 ; return 0;}
if(n==4893){ cout << 4026871 ; return 0;}
if(n==4894){ cout << 4027789 ; return 0;}
if(n==4895){ cout << 4029954 ; return 0;}
if(n==4896){ cout << 4030064 ; return 0;}
if(n==4897){ cout << 4032010 ; return 0;}
if(n==4898){ cout << 4033012 ; return 0;}
if(n==4899){ cout << 4036434 ; return 0;}
if(n==4900){ cout << 4037040 ; return 0;}
if(n==4901){ cout << 4038867 ; return 0;}
if(n==4902){ cout << 4040645 ; return 0;}
if(n==4903){ cout << 4042484 ; return 0;}
if(n==4904){ cout << 4042712 ; return 0;}
if(n==4905){ cout << 4046181 ; return 0;}
if(n==4906){ cout << 4047278 ; return 0;}
if(n==4907){ cout << 4049642 ; return 0;}
if(n==4908){ cout << 4050409 ; return 0;}
if(n==4909){ cout << 4052248 ; return 0;}
if(n==4910){ cout << 4053171 ; return 0;}
if(n==4911){ cout << 4056239 ; return 0;}
if(n==4912){ cout << 4056355 ; return 0;}
if(n==4913){ cout << 4058194 ; return 0;}
if(n==4914){ cout << 4060519 ; return 0;}
if(n==4915){ cout << 4062364 ; return 0;}
if(n==4916){ cout << 4062823 ; return 0;}
if(n==4917){ cout << 4066455 ; return 0;}
if(n==4918){ cout << 4067378 ; return 0;}
if(n==4919){ cout << 4069223 ; return 0;}
if(n==4920){ cout << 4069603 ; return 0;}
if(n==4921){ cout << 4072224 ; return 0;}
if(n==4922){ cout << 4073246 ; return 0;}
if(n==4923){ cout << 4076749 ; return 0;}
if(n==4924){ cout << 4077211 ; return 0;}
if(n==4925){ cout << 4079047 ; return 0;}
if(n==4926){ cout << 4080585 ; return 0;}
if(n==4927){ cout << 4082441 ; return 0;}
if(n==4928){ cout << 4082485 ; return 0;}
if(n==4929){ cout << 4085763 ; return 0;}
if(n==4930){ cout << 4086668 ; return 0;}
if(n==4931){ cout << 4088518 ; return 0;}
if(n==4932){ cout << 4089393 ; return 0;}
if(n==4933){ cout << 4091241 ; return 0;}
if(n==4934){ cout << 4092167 ; return 0;}
if(n==4935){ cout << 4096300 ; return 0;}
if(n==4936){ cout << 4096530 ; return 0;}
if(n==4937){ cout << 4098380 ; return 0;}
if(n==4938){ cout << 4099927 ; return 0;}
if(n==4939){ cout << 4102116 ; return 0;}
if(n==4940){ cout << 4102622 ; return 0;}
if(n==4941){ cout << 4106305 ; return 0;}
if(n==4942){ cout << 4107495 ; return 0;}
if(n==4943){ cout << 4109349 ; return 0;}
if(n==4944){ cout << 4109546 ; return 0;}
if(n==4945){ cout << 4111654 ; return 0;}
if(n==4946){ cout << 4112580 ; return 0;}
if(n==4947){ cout << 4115672 ; return 0;}
if(n==4948){ cout << 4116134 ; return 0;}
if(n==4949){ cout << 4118594 ; return 0;}
if(n==4950){ cout << 4120666 ; return 0;}
if(n==4951){ cout << 4122523 ; return 0;}
if(n==4952){ cout << 4122756 ; return 0;}
if(n==4953){ cout << 4125899 ; return 0;}
if(n==4954){ cout << 4126826 ; return 0;}
if(n==4955){ cout << 4128686 ; return 0;}
if(n==4956){ cout << 4129717 ; return 0;}
if(n==4957){ cout << 4131574 ; return 0;}
if(n==4958){ cout << 4132530 ; return 0;}
if(n==4959){ cout << 4136414 ; return 0;}
if(n==4960){ cout << 4136474 ; return 0;}
if(n==4961){ cout << 4138705 ; return 0;}
if(n==4962){ cout << 4140261 ; return 0;}
if(n==4963){ cout << 4142652 ; return 0;}
if(n==4964){ cout << 4143113 ; return 0;}
if(n==4965){ cout << 4146235 ; return 0;}
if(n==4966){ cout << 4147174 ; return 0;}
if(n==4967){ cout << 4149037 ; return 0;}
if(n==4968){ cout << 4149535 ; return 0;}
if(n==4969){ cout << 4151397 ; return 0;}
if(n==4970){ cout << 4152627 ; return 0;}
if(n==4971){ cout << 4155734 ; return 0;}
if(n==4972){ cout << 4156285 ; return 0;}
if(n==4973){ cout << 4158148 ; return 0;}
if(n==4974){ cout << 4159701 ; return 0;}
if(n==4975){ cout << 4161582 ; return 0;}
if(n==4976){ cout << 4161699 ; return 0;}
if(n==4977){ cout << 4166347 ; return 0;}
if(n==4978){ cout << 4167396 ; return 0;}
if(n==4979){ cout << 4169271 ; return 0;}
if(n==4980){ cout << 4170068 ; return 0;}
if(n==4981){ cout << 4171930 ; return 0;}
if(n==4982){ cout << 4172902 ; return 0;}
if(n==4983){ cout << 4176633 ; return 0;}
if(n==4984){ cout << 4176932 ; return 0;}
if(n==4985){ cout << 4178795 ; return 0;}
if(n==4986){ cout << 4180560 ; return 0;}
if(n==4987){ cout << 4182431 ; return 0;}
if(n==4988){ cout << 4182919 ; return 0;}
if(n==4989){ cout << 4186041 ; return 0;}
if(n==4990){ cout << 4186979 ; return 0;}
if(n==4991){ cout << 4189763 ; return 0;}
if(n==4992){ cout << 4189786 ; return 0;}
if(n==4993){ cout << 4191657 ; return 0;}
if(n==4994){ cout << 4192775 ; return 0;}
if(n==4995){ cout << 4196447 ; return 0;}
if(n==4996){ cout << 4196914 ; return 0;}
if(n==4997){ cout << 4199001 ; return 0;}
if(n==4998){ cout << 4201073 ; return 0;}
if(n==4999){ cout << 4202948 ; return 0;}
if(n==5000){ cout << 4203176 ; return 0;}
}

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  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
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055

/* kod generujący ten kod:
#include "bits/stdc++.h"

#define int long long
#define pi pair<long long, long long>
#define a3 array<long long, 3>

#define meow main

using namespace std;

signed meow() {
 // cin.tie((ostream *)!ios::sync_with_stdio(false));
  int n;
  cin >> n;

  unordered_map<int, int> squares;
  for (int i = 1; i*i < n*n; i++)
    for (int j = i; j*j + i*i <= n*n; j++)
      squares[i * i + j * j]++;

  int res = 0;
  for(int k=1; k<=n; k++) {
    for (int i = 1; i * i < n*n; i++)
      res += squares[k*k - i * i];

    cout << "if(n=="<<k<<"){ cout << " <<res << " ; return 0;}\n";
  }

  cout << res << '\n';
}

*/
#include <bits/stdc++.h>

using namespace std;

int main() {
int n; cin >> n;
if(n<= 3001) {

  unordered_map<int, int> squares;
  for (int i = 1; i*i < n*n; i++)
    for (int j = i; j*j + i*i <= n*n; j++)
      squares[i * i + j * j]++;

  int res = 0;
  for(int k=1; k<=n; k++) {
    for (int i = 1; i * i < n*n; i++)
      res += squares[k*k - i * i];
  }

  cout << res << '\n';
  return 0;
}
if(n==3002){ cout << 1513449 ; return 0;}
if(n==3003){ cout << 1516301 ; return 0;}
if(n==3004){ cout << 1516583 ; return 0;}
if(n==3005){ cout << 1517704 ; return 0;}
if(n==3006){ cout << 1518782 ; return 0;}
if(n==3007){ cout << 1519981 ; return 0;}
if(n==3008){ cout << 1519999 ; return 0;}
if(n==3009){ cout << 1521948 ; return 0;}
if(n==3010){ cout << 1522706 ; return 0;}
if(n==3011){ cout << 1523836 ; return 0;}
if(n==3012){ cout << 1524312 ; return 0;}
if(n==3013){ cout << 1525559 ; return 0;}
if(n==3014){ cout << 1526227 ; return 0;}
if(n==3015){ cout << 1528428 ; return 0;}
if(n==3016){ cout << 1528563 ; return 0;}
if(n==3017){ cout << 1530024 ; return 0;}
if(n==3018){ cout << 1530971 ; return 0;}
if(n==3019){ cout << 1532104 ; return 0;}
if(n==3020){ cout << 1532389 ; return 0;}
if(n==3021){ cout << 1534476 ; return 0;}
if(n==3022){ cout << 1535043 ; return 0;}
if(n==3023){ cout << 1536177 ; return 0;}
if(n==3024){ cout << 1536357 ; return 0;}
if(n==3025){ cout << 1537714 ; return 0;}
if(n==3026){ cout << 1538277 ; return 0;}
if(n==3027){ cout << 1540169 ; return 0;}
if(n==3028){ cout << 1540451 ; return 0;}
if(n==3029){ cout << 1541581 ; return 0;}
if(n==3030){ cout << 1542522 ; return 0;}
if(n==3031){ cout << 1543982 ; return 0;}
if(n==3032){ cout << 1544125 ; return 0;}
if(n==3033){ cout << 1546275 ; return 0;}
if(n==3034){ cout << 1546838 ; return 0;}
if(n==3035){ cout << 1547978 ; return 0;}
if(n==3036){ cout << 1548589 ; return 0;}
if(n==3037){ cout << 1549726 ; return 0;}
if(n==3038){ cout << 1550530 ; return 0;}
if(n==3039){ cout << 1552428 ; return 0;}
if(n==3040){ cout << 1552466 ; return 0;}
if(n==3041){ cout << 1553605 ; return 0;}
if(n==3042){ cout << 1554680 ; return 0;}
if(n==3043){ cout << 1555834 ; return 0;}
if(n==3044){ cout << 1556118 ; return 0;}
if(n==3045){ cout << 1558559 ; return 0;}
if(n==3046){ cout << 1559131 ; return 0;}
if(n==3047){ cout << 1560480 ; return 0;}
if(n==3048){ cout << 1560722 ; return 0;}
if(n==3049){ cout << 1561864 ; return 0;}
if(n==3050){ cout << 1562425 ; return 0;}
if(n==3051){ cout << 1564674 ; return 0;}
if(n==3052){ cout << 1565040 ; return 0;}
if(n==3053){ cout << 1566272 ; return 0;}
if(n==3054){ cout << 1567225 ; return 0;}
if(n==3055){ cout << 1568413 ; return 0;}
if(n==3056){ cout << 1568485 ; return 0;}
if(n==3057){ cout << 1570401 ; return 0;}
if(n==3058){ cout << 1571090 ; return 0;}
if(n==3059){ cout << 1572862 ; return 0;}
if(n==3060){ cout << 1573401 ; return 0;}
if(n==3061){ cout << 1574547 ; return 0;}
if(n==3062){ cout << 1575122 ; return 0;}
if(n==3063){ cout << 1577035 ; return 0;}
if(n==3064){ cout << 1577179 ; return 0;}
if(n==3065){ cout << 1578322 ; return 0;}
if(n==3066){ cout << 1579554 ; return 0;}
if(n==3067){ cout << 1580705 ; return 0;}
if(n==3068){ cout << 1581001 ; return 0;}
if(n==3069){ cout << 1583739 ; return 0;}
if(n==3070){ cout << 1584317 ; return 0;}
if(n==3071){ cout << 1585495 ; return 0;}
if(n==3072){ cout << 1585497 ; return 0;}
if(n==3073){ cout << 1586985 ; return 0;}
if(n==3074){ cout << 1587555 ; return 0;}
if(n==3075){ cout << 1589468 ; return 0;}
if(n==3076){ cout << 1589755 ; return 0;}
if(n==3077){ cout << 1590903 ; return 0;}
if(n==3078){ cout << 1592177 ; return 0;}
if(n==3079){ cout << 1593332 ; return 0;}
if(n==3080){ cout << 1593550 ; return 0;}
if(n==3081){ cout << 1595523 ; return 0;}
if(n==3082){ cout << 1596170 ; return 0;}
if(n==3083){ cout << 1597327 ; return 0;}
if(n==3084){ cout << 1597809 ; return 0;}
if(n==3085){ cout << 1598960 ; return 0;}
if(n==3086){ cout << 1599539 ; return 0;}
if(n==3087){ cout << 1602453 ; return 0;}
if(n==3088){ cout << 1602524 ; return 0;}
if(n==3089){ cout << 1603681 ; return 0;}
if(n==3090){ cout << 1604664 ; return 0;}
if(n==3091){ cout << 1606034 ; return 0;}
if(n==3092){ cout << 1606322 ; return 0;}
if(n==3093){ cout << 1608259 ; return 0;}
if(n==3094){ cout << 1608999 ; return 0;}
if(n==3095){ cout << 1610162 ; return 0;}
if(n==3096){ cout << 1610452 ; return 0;}
if(n==3097){ cout << 1611753 ; return 0;}
if(n==3098){ cout << 1612332 ; return 0;}
if(n==3099){ cout << 1614269 ; return 0;}
if(n==3100){ cout << 1614575 ; return 0;}
if(n==3101){ cout << 1616077 ; return 0;}
if(n==3102){ cout << 1617273 ; return 0;}
if(n==3103){ cout << 1618457 ; return 0;}
if(n==3104){ cout << 1618492 ; return 0;}
if(n==3105){ cout << 1620976 ; return 0;}
if(n==3106){ cout << 1621557 ; return 0;}
if(n==3107){ cout << 1622730 ; return 0;}
if(n==3108){ cout << 1623353 ; return 0;}
if(n==3109){ cout << 1624517 ; return 0;}
if(n==3110){ cout << 1625102 ; return 0;}
if(n==3111){ cout << 1627042 ; return 0;}
if(n==3112){ cout << 1627186 ; return 0;}
if(n==3113){ cout << 1628577 ; return 0;}
if(n==3114){ cout << 1629679 ; return 0;}
if(n==3115){ cout << 1631175 ; return 0;}
if(n==3116){ cout << 1631498 ; return 0;}
if(n==3117){ cout << 1633450 ; return 0;}
if(n==3118){ cout << 1634035 ; return 0;}
if(n==3119){ cout << 1635205 ; return 0;}
if(n==3120){ cout << 1635321 ; return 0;}
if(n==3121){ cout << 1636490 ; return 0;}
if(n==3122){ cout << 1637249 ; return 0;}
if(n==3123){ cout << 1639477 ; return 0;}
if(n==3124){ cout << 1639833 ; return 0;}
if(n==3125){ cout << 1640997 ; return 0;}
if(n==3126){ cout << 1641974 ; return 0;}
if(n==3127){ cout << 1643185 ; return 0;}
if(n==3128){ cout << 1643343 ; return 0;}
if(n==3129){ cout << 1645856 ; return 0;}
if(n==3130){ cout << 1646437 ; return 0;}
if(n==3131){ cout << 1647685 ; return 0;}
if(n==3132){ cout << 1648261 ; return 0;}
if(n==3133){ cout << 1649430 ; return 0;}
if(n==3134){ cout << 1650018 ; return 0;}
if(n==3135){ cout << 1652582 ; return 0;}
if(n==3136){ cout << 1652606 ; return 0;}
if(n==3137){ cout << 1653781 ; return 0;}
if(n==3138){ cout << 1654767 ; return 0;}
if(n==3139){ cout << 1655999 ; return 0;}
if(n==3140){ cout << 1656287 ; return 0;}
if(n==3141){ cout << 1658511 ; return 0;}
if(n==3142){ cout << 1659101 ; return 0;}
if(n==3143){ cout << 1660615 ; return 0;}
if(n==3144){ cout << 1660866 ; return 0;}
if(n==3145){ cout << 1662026 ; return 0;}
if(n==3146){ cout << 1662732 ; return 0;}
if(n==3147){ cout << 1664699 ; return 0;}
if(n==3148){ cout << 1664995 ; return 0;}
if(n==3149){ cout << 1666263 ; return 0;}
if(n==3150){ cout << 1667695 ; return 0;}
if(n==3151){ cout << 1668978 ; return 0;}
if(n==3152){ cout << 1669050 ; return 0;}
if(n==3153){ cout << 1671026 ; return 0;}
if(n==3154){ cout << 1671697 ; return 0;}
if(n==3155){ cout << 1672882 ; return 0;}
if(n==3156){ cout << 1673379 ; return 0;}
if(n==3157){ cout << 1675178 ; return 0;}
if(n==3158){ cout << 1675771 ; return 0;}
if(n==3159){ cout << 1678136 ; return 0;}
if(n==3160){ cout << 1678286 ; return 0;}
if(n==3161){ cout << 1679465 ; return 0;}
if(n==3162){ cout << 1680517 ; return 0;}
if(n==3163){ cout << 1681704 ; return 0;}
if(n==3164){ cout << 1682084 ; return 0;}
if(n==3165){ cout << 1684081 ; return 0;}
if(n==3166){ cout << 1684675 ; return 0;}
if(n==3167){ cout << 1685863 ; return 0;}
if(n==3168){ cout << 1685949 ; return 0;}
if(n==3169){ cout << 1687136 ; return 0;}
if(n==3170){ cout << 1687724 ; return 0;}
if(n==3171){ cout << 1690306 ; return 0;}
if(n==3172){ cout << 1690597 ; return 0;}
if(n==3173){ cout << 1691928 ; return 0;}
if(n==3174){ cout << 1693010 ; return 0;}
if(n==3175){ cout << 1694216 ; return 0;}
if(n==3176){ cout << 1694363 ; return 0;}
if(n==3177){ cout << 1696615 ; return 0;}
if(n==3178){ cout << 1697388 ; return 0;}
if(n==3179){ cout << 1698797 ; return 0;}
if(n==3180){ cout << 1699288 ; return 0;}
if(n==3181){ cout << 1700479 ; return 0;}
if(n==3182){ cout << 1701102 ; return 0;}
if(n==3183){ cout << 1703090 ; return 0;}
if(n==3184){ cout << 1703165 ; return 0;}
if(n==3185){ cout << 1704743 ; return 0;}
if(n==3186){ cout << 1705960 ; return 0;}
if(n==3187){ cout << 1707156 ; return 0;}
if(n==3188){ cout << 1707453 ; return 0;}
if(n==3189){ cout << 1709450 ; return 0;}
if(n==3190){ cout << 1710151 ; return 0;}
if(n==3191){ cout << 1711348 ; return 0;}
if(n==3192){ cout << 1711704 ; return 0;}
if(n==3193){ cout << 1713003 ; return 0;}
if(n==3194){ cout << 1713600 ; return 0;}
if(n==3195){ cout << 1715926 ; return 0;}
if(n==3196){ cout << 1716237 ; return 0;}
if(n==3197){ cout << 1717559 ; return 0;}
if(n==3198){ cout << 1718554 ; return 0;}
if(n==3199){ cout << 1720095 ; return 0;}
if(n==3200){ cout << 1720101 ; return 0;}
if(n==3201){ cout << 1722470 ; return 0;}
if(n==3202){ cout << 1723069 ; return 0;}
if(n==3203){ cout << 1724271 ; return 0;}
if(n==3204){ cout << 1724840 ; return 0;}
if(n==3205){ cout << 1726036 ; return 0;}
if(n==3206){ cout << 1726807 ; return 0;}
if(n==3207){ cout << 1728810 ; return 0;}
if(n==3208){ cout << 1728959 ; return 0;}
if(n==3209){ cout << 1730161 ; return 0;}
if(n==3210){ cout << 1731183 ; return 0;}
if(n==3211){ cout << 1732511 ; return 0;}
if(n==3212){ cout << 1732867 ; return 0;}
if(n==3213){ cout << 1735911 ; return 0;}
if(n==3214){ cout << 1736514 ; return 0;}
if(n==3215){ cout << 1737722 ; return 0;}
if(n==3216){ cout << 1737853 ; return 0;}
if(n==3217){ cout << 1739058 ; return 0;}
if(n==3218){ cout << 1739660 ; return 0;}
if(n==3219){ cout << 1741666 ; return 0;}
if(n==3220){ cout << 1742086 ; return 0;}
if(n==3221){ cout << 1743292 ; return 0;}
if(n==3222){ cout << 1744449 ; return 0;}
if(n==3223){ cout << 1745876 ; return 0;}
if(n==3224){ cout << 1746035 ; return 0;}
if(n==3225){ cout << 1748143 ; return 0;}
if(n==3226){ cout << 1748746 ; return 0;}
if(n==3227){ cout << 1750300 ; return 0;}
if(n==3228){ cout << 1750803 ; return 0;}
if(n==3229){ cout << 1752012 ; return 0;}
if(n==3230){ cout << 1752677 ; return 0;}
if(n==3231){ cout << 1754979 ; return 0;}
if(n==3232){ cout << 1755015 ; return 0;}
if(n==3233){ cout << 1756221 ; return 0;}
if(n==3234){ cout << 1757807 ; return 0;}
if(n==3235){ cout << 1759022 ; return 0;}
if(n==3236){ cout << 1759324 ; return 0;}
if(n==3237){ cout << 1761396 ; return 0;}
if(n==3238){ cout << 1762004 ; return 0;}
if(n==3239){ cout << 1763248 ; return 0;}
if(n==3240){ cout << 1763550 ; return 0;}
if(n==3241){ cout << 1765119 ; return 0;}
if(n==3242){ cout << 1765725 ; return 0;}
if(n==3243){ cout << 1768022 ; return 0;}
if(n==3244){ cout << 1768327 ; return 0;}
if(n==3245){ cout << 1769814 ; return 0;}
if(n==3246){ cout << 1770827 ; return 0;}
if(n==3247){ cout << 1772056 ; return 0;}
if(n==3248){ cout << 1772152 ; return 0;}
if(n==3249){ cout << 1774714 ; return 0;}
if(n==3250){ cout << 1775308 ; return 0;}
if(n==3251){ cout << 1776528 ; return 0;}
if(n==3252){ cout << 1777040 ; return 0;}
if(n==3253){ cout << 1778258 ; return 0;}
if(n==3254){ cout << 1778869 ; return 0;}
if(n==3255){ cout << 1781652 ; return 0;}
if(n==3256){ cout << 1781831 ; return 0;}
if(n==3257){ cout << 1783051 ; return 0;}
if(n==3258){ cout << 1784204 ; return 0;}
if(n==3259){ cout << 1785427 ; return 0;}
if(n==3260){ cout << 1785735 ; return 0;}
if(n==3261){ cout << 1787777 ; return 0;}
if(n==3262){ cout << 1788562 ; return 0;}
if(n==3263){ cout << 1789794 ; return 0;}
if(n==3264){ cout << 1789826 ; return 0;}
if(n==3265){ cout << 1791044 ; return 0;}
if(n==3266){ cout << 1791728 ; return 0;}
if(n==3267){ cout << 1794618 ; return 0;}
if(n==3268){ cout << 1794974 ; return 0;}
if(n==3269){ cout << 1796557 ; return 0;}
if(n==3270){ cout << 1797573 ; return 0;}
if(n==3271){ cout << 1798800 ; return 0;}
if(n==3272){ cout << 1798952 ; return 0;}
if(n==3273){ cout << 1801003 ; return 0;}
if(n==3274){ cout << 1801615 ; return 0;}
if(n==3275){ cout << 1802859 ; return 0;}
if(n==3276){ cout << 1803604 ; return 0;}
if(n==3277){ cout << 1804827 ; return 0;}
if(n==3278){ cout << 1805552 ; return 0;}
if(n==3279){ cout << 1807600 ; return 0;}
if(n==3280){ cout << 1807671 ; return 0;}
if(n==3281){ cout << 1808897 ; return 0;}
if(n==3282){ cout << 1809928 ; return 0;}
if(n==3283){ cout << 1811610 ; return 0;}
if(n==3284){ cout << 1811916 ; return 0;}
if(n==3285){ cout << 1814240 ; return 0;}
if(n==3286){ cout << 1814894 ; return 0;}
if(n==3287){ cout << 1816255 ; return 0;}
if(n==3288){ cout << 1816512 ; return 0;}
if(n==3289){ cout << 1818095 ; return 0;}
if(n==3290){ cout << 1818920 ; return 0;}
if(n==3291){ cout << 1820977 ; return 0;}
if(n==3292){ cout << 1821286 ; return 0;}
if(n==3293){ cout << 1822515 ; return 0;}
if(n==3294){ cout << 1823727 ; return 0;}
if(n==3295){ cout << 1824965 ; return 0;}
if(n==3296){ cout << 1825004 ; return 0;}
if(n==3297){ cout << 1827652 ; return 0;}
if(n==3298){ cout << 1828266 ; return 0;}
if(n==3299){ cout << 1829504 ; return 0;}
if(n==3300){ cout << 1830112 ; return 0;}
if(n==3301){ cout << 1831348 ; return 0;}
if(n==3302){ cout << 1831975 ; return 0;}
if(n==3303){ cout << 1834328 ; return 0;}
if(n==3304){ cout << 1834534 ; return 0;}
if(n==3305){ cout << 1835767 ; return 0;}
if(n==3306){ cout << 1836909 ; return 0;}
if(n==3307){ cout << 1838150 ; return 0;}
if(n==3308){ cout << 1838461 ; return 0;}
if(n==3309){ cout << 1840533 ; return 0;}
if(n==3310){ cout << 1841156 ; return 0;}
if(n==3311){ cout << 1843132 ; return 0;}
if(n==3312){ cout << 1843292 ; return 0;}
if(n==3313){ cout << 1844533 ; return 0;}
if(n==3314){ cout << 1845153 ; return 0;}
if(n==3315){ cout << 1847207 ; return 0;}
if(n==3316){ cout << 1847516 ; return 0;}
if(n==3317){ cout << 1848865 ; return 0;}
if(n==3318){ cout << 1850232 ; return 0;}
if(n==3319){ cout << 1851477 ; return 0;}
if(n==3320){ cout << 1851635 ; return 0;}
if(n==3321){ cout << 1854115 ; return 0;}
if(n==3322){ cout << 1854861 ; return 0;}
if(n==3323){ cout << 1856108 ; return 0;}
if(n==3324){ cout << 1856626 ; return 0;}
if(n==3325){ cout << 1858395 ; return 0;}
if(n==3326){ cout << 1859019 ; return 0;}
if(n==3327){ cout << 1861097 ; return 0;}
if(n==3328){ cout << 1861100 ; return 0;}
if(n==3329){ cout << 1862347 ; return 0;}
if(n==3330){ cout << 1863521 ; return 0;}
if(n==3331){ cout << 1864771 ; return 0;}
if(n==3332){ cout << 1865184 ; return 0;}
if(n==3333){ cout << 1867646 ; return 0;}
if(n==3334){ cout << 1868272 ; return 0;}
if(n==3335){ cout << 1869625 ; return 0;}
if(n==3336){ cout << 1869891 ; return 0;}
if(n==3337){ cout << 1871232 ; return 0;}
if(n==3338){ cout << 1871856 ; return 0;}
if(n==3339){ cout << 1874896 ; return 0;}
if(n==3340){ cout << 1875211 ; return 0;}
if(n==3341){ cout << 1876458 ; return 0;}
if(n==3342){ cout << 1877501 ; return 0;}
if(n==3343){ cout << 1878755 ; return 0;}
if(n==3344){ cout << 1878859 ; return 0;}
if(n==3345){ cout << 1880967 ; return 0;}
if(n==3346){ cout << 1881780 ; return 0;}
if(n==3347){ cout << 1883036 ; return 0;}
if(n==3348){ cout << 1883693 ; return 0;}
if(n==3349){ cout << 1884943 ; return 0;}
if(n==3350){ cout << 1885587 ; return 0;}
if(n==3351){ cout << 1887680 ; return 0;}
if(n==3352){ cout << 1887838 ; return 0;}
if(n==3353){ cout << 1889461 ; return 0;}
if(n==3354){ cout << 1890558 ; return 0;}
if(n==3355){ cout << 1892039 ; return 0;}
if(n==3356){ cout << 1892354 ; return 0;}
if(n==3357){ cout << 1894731 ; return 0;}
if(n==3358){ cout << 1895414 ; return 0;}
if(n==3359){ cout << 1896674 ; return 0;}
if(n==3360){ cout << 1896757 ; return 0;}
if(n==3361){ cout << 1898016 ; return 0;}
if(n==3362){ cout << 1898644 ; return 0;}
if(n==3363){ cout << 1901052 ; return 0;}
if(n==3364){ cout << 1901364 ; return 0;}
if(n==3365){ cout << 1902620 ; return 0;}
if(n==3366){ cout << 1904038 ; return 0;}
if(n==3367){ cout << 1905655 ; return 0;}
if(n==3368){ cout << 1905811 ; return 0;}
if(n==3369){ cout << 1907922 ; return 0;}
if(n==3370){ cout << 1908548 ; return 0;}
if(n==3371){ cout << 1909813 ; return 0;}
if(n==3372){ cout << 1910340 ; return 0;}
if(n==3373){ cout << 1911603 ; return 0;}
if(n==3374){ cout << 1912415 ; return 0;}
if(n==3375){ cout << 1914896 ; return 0;}
if(n==3376){ cout << 1914976 ; return 0;}
if(n==3377){ cout << 1916484 ; return 0;}
if(n==3378){ cout << 1917545 ; return 0;}
if(n==3379){ cout << 1918892 ; return 0;}
if(n==3380){ cout << 1919198 ; return 0;}
if(n==3381){ cout << 1922245 ; return 0;}
if(n==3382){ cout << 1922946 ; return 0;}
if(n==3383){ cout << 1924226 ; return 0;}
if(n==3384){ cout << 1924539 ; return 0;}
if(n==3385){ cout << 1925802 ; return 0;}
if(n==3386){ cout << 1926435 ; return 0;}
if(n==3387){ cout << 1928552 ; return 0;}
if(n==3388){ cout << 1929042 ; return 0;}
if(n==3389){ cout << 1930311 ; return 0;}
if(n==3390){ cout << 1931366 ; return 0;}
if(n==3391){ cout << 1932638 ; return 0;}
if(n==3392){ cout << 1932656 ; return 0;}
if(n==3393){ cout << 1935054 ; return 0;}
if(n==3394){ cout << 1935689 ; return 0;}
if(n==3395){ cout << 1937320 ; return 0;}
if(n==3396){ cout << 1937856 ; return 0;}
if(n==3397){ cout << 1939223 ; return 0;}
if(n==3398){ cout << 1939861 ; return 0;}
if(n==3399){ cout << 1942422 ; return 0;}
if(n==3400){ cout << 1942571 ; return 0;}
if(n==3401){ cout << 1943998 ; return 0;}
if(n==3402){ cout << 1945637 ; return 0;}
if(n==3403){ cout << 1946944 ; return 0;}
if(n==3404){ cout << 1947289 ; return 0;}
if(n==3405){ cout << 1949436 ; return 0;}
if(n==3406){ cout << 1950083 ; return 0;}
if(n==3407){ cout << 1951361 ; return 0;}
if(n==3408){ cout << 1951498 ; return 0;}
if(n==3409){ cout << 1953148 ; return 0;}
if(n==3410){ cout << 1953951 ; return 0;}
if(n==3411){ cout << 1956383 ; return 0;}
if(n==3412){ cout << 1956701 ; return 0;}
if(n==3413){ cout << 1957979 ; return 0;}
if(n==3414){ cout << 1959046 ; return 0;}
if(n==3415){ cout << 1960329 ; return 0;}
if(n==3416){ cout << 1960533 ; return 0;}
if(n==3417){ cout << 1962737 ; return 0;}
if(n==3418){ cout << 1963376 ; return 0;}
if(n==3419){ cout << 1964666 ; return 0;}
if(n==3420){ cout << 1965337 ; return 0;}
if(n==3421){ cout << 1966863 ; return 0;}
if(n==3422){ cout << 1967525 ; return 0;}
if(n==3423){ cout << 1970311 ; return 0;}
if(n==3424){ cout << 1970352 ; return 0;}
if(n==3425){ cout << 1971626 ; return 0;}
if(n==3426){ cout << 1972702 ; return 0;}
if(n==3427){ cout << 1974097 ; return 0;}
if(n==3428){ cout << 1974417 ; return 0;}
if(n==3429){ cout << 1976982 ; return 0;}
if(n==3430){ cout << 1977837 ; return 0;}
if(n==3431){ cout << 1979177 ; return 0;}
if(n==3432){ cout << 1979494 ; return 0;}
if(n==3433){ cout << 1980780 ; return 0;}
if(n==3434){ cout << 1981418 ; return 0;}
if(n==3435){ cout << 1983559 ; return 0;}
if(n==3436){ cout << 1983882 ; return 0;}
if(n==3437){ cout << 1985546 ; return 0;}
if(n==3438){ cout << 1986777 ; return 0;}
if(n==3439){ cout << 1988201 ; return 0;}
if(n==3440){ cout << 1988284 ; return 0;}
if(n==3441){ cout << 1990572 ; return 0;}
if(n==3442){ cout << 1991216 ; return 0;}
if(n==3443){ cout << 1992742 ; return 0;}
if(n==3444){ cout << 1993434 ; return 0;}
if(n==3445){ cout << 1994706 ; return 0;}
if(n==3446){ cout << 1995353 ; return 0;}
if(n==3447){ cout << 1997808 ; return 0;}
if(n==3448){ cout << 1997970 ; return 0;}
if(n==3449){ cout << 1999262 ; return 0;}
if(n==3450){ cout << 2000431 ; return 0;}
if(n==3451){ cout << 2002089 ; return 0;}
if(n==3452){ cout << 2002413 ; return 0;}
if(n==3453){ cout << 2004575 ; return 0;}
if(n==3454){ cout << 2005339 ; return 0;}
if(n==3455){ cout << 2006637 ; return 0;}
if(n==3456){ cout << 2006658 ; return 0;}
if(n==3457){ cout << 2007953 ; return 0;}
if(n==3458){ cout << 2008873 ; return 0;}
if(n==3459){ cout << 2011035 ; return 0;}
if(n==3460){ cout << 2011353 ; return 0;}
if(n==3461){ cout << 2012649 ; return 0;}
if(n==3462){ cout << 2013731 ; return 0;}
if(n==3463){ cout << 2015030 ; return 0;}
if(n==3464){ cout << 2015191 ; return 0;}
if(n==3465){ cout << 2018922 ; return 0;}
if(n==3466){ cout << 2019570 ; return 0;}
if(n==3467){ cout << 2020871 ; return 0;}
if(n==3468){ cout << 2021413 ; return 0;}
if(n==3469){ cout << 2022712 ; return 0;}
if(n==3470){ cout << 2023365 ; return 0;}
if(n==3471){ cout << 2025530 ; return 0;}
if(n==3472){ cout << 2025641 ; return 0;}
if(n==3473){ cout << 2027075 ; return 0;}
if(n==3474){ cout << 2028307 ; return 0;}
if(n==3475){ cout << 2029626 ; return 0;}
if(n==3476){ cout << 2030021 ; return 0;}
if(n==3477){ cout << 2032423 ; return 0;}
if(n==3478){ cout << 2033101 ; return 0;}
if(n==3479){ cout << 2034880 ; return 0;}
if(n==3480){ cout << 2035146 ; return 0;}
if(n==3481){ cout << 2036497 ; return 0;}
if(n==3482){ cout << 2037148 ; return 0;}
if(n==3483){ cout << 2039871 ; return 0;}
if(n==3484){ cout << 2040206 ; return 0;}
if(n==3485){ cout << 2041495 ; return 0;}
if(n==3486){ cout << 2042931 ; return 0;}
if(n==3487){ cout << 2044475 ; return 0;}
if(n==3488){ cout << 2044514 ; return 0;}
if(n==3489){ cout << 2046700 ; return 0;}
if(n==3490){ cout << 2047348 ; return 0;}
if(n==3491){ cout << 2048658 ; return 0;}
if(n==3492){ cout << 2049278 ; return 0;}
if(n==3493){ cout << 2050969 ; return 0;}
if(n==3494){ cout << 2051625 ; return 0;}
if(n==3495){ cout << 2053805 ; return 0;}
if(n==3496){ cout << 2054002 ; return 0;}
if(n==3497){ cout << 2055307 ; return 0;}
if(n==3498){ cout << 2056599 ; return 0;}
if(n==3499){ cout << 2057912 ; return 0;}
if(n==3500){ cout << 2058329 ; return 0;}
if(n==3501){ cout << 2060808 ; return 0;}
if(n==3502){ cout << 2061476 ; return 0;}
if(n==3503){ cout << 2062873 ; return 0;}
if(n==3504){ cout << 2063010 ; return 0;}
if(n==3505){ cout << 2064318 ; return 0;}
if(n==3506){ cout << 2064974 ; return 0;}
if(n==3507){ cout << 2067826 ; return 0;}
if(n==3508){ cout << 2068153 ; return 0;}
if(n==3509){ cout << 2069729 ; return 0;}
if(n==3510){ cout << 2071016 ; return 0;}
if(n==3511){ cout << 2072333 ; return 0;}
if(n==3512){ cout << 2072498 ; return 0;}
if(n==3513){ cout << 2074699 ; return 0;}
if(n==3514){ cout << 2075553 ; return 0;}
if(n==3515){ cout << 2077004 ; return 0;}
if(n==3516){ cout << 2077552 ; return 0;}
if(n==3517){ cout << 2078869 ; return 0;}
if(n==3518){ cout << 2079529 ; return 0;}
if(n==3519){ cout << 2082240 ; return 0;}
if(n==3520){ cout << 2082263 ; return 0;}
if(n==3521){ cout << 2083967 ; return 0;}
if(n==3522){ cout << 2085073 ; return 0;}
if(n==3523){ cout << 2086402 ; return 0;}
if(n==3524){ cout << 2086731 ; return 0;}
if(n==3525){ cout << 2089025 ; return 0;}
if(n==3526){ cout << 2089717 ; return 0;}
if(n==3527){ cout << 2091040 ; return 0;}
if(n==3528){ cout << 2091455 ; return 0;}
if(n==3529){ cout << 2092777 ; return 0;}
if(n==3530){ cout << 2093433 ; return 0;}
if(n==3531){ cout << 2096096 ; return 0;}
if(n==3532){ cout << 2096428 ; return 0;}
if(n==3533){ cout << 2097751 ; return 0;}
if(n==3534){ cout << 2099052 ; return 0;}
if(n==3535){ cout << 2100750 ; return 0;}
if(n==3536){ cout << 2100827 ; return 0;}
if(n==3537){ cout << 2103475 ; return 0;}
if(n==3538){ cout << 2104132 ; return 0;}
if(n==3539){ cout << 2105460 ; return 0;}
if(n==3540){ cout << 2106032 ; return 0;}
if(n==3541){ cout << 2107358 ; return 0;}
if(n==3542){ cout << 2108455 ; return 0;}
if(n==3543){ cout << 2110668 ; return 0;}
if(n==3544){ cout << 2110835 ; return 0;}
if(n==3545){ cout << 2112158 ; return 0;}
if(n==3546){ cout << 2113413 ; return 0;}
if(n==3547){ cout << 2114744 ; return 0;}
if(n==3548){ cout << 2115077 ; return 0;}
if(n==3549){ cout << 2117926 ; return 0;}
if(n==3550){ cout << 2118607 ; return 0;}
if(n==3551){ cout << 2119977 ; return 0;}
if(n==3552){ cout << 2120045 ; return 0;}
if(n==3553){ cout << 2121790 ; return 0;}
if(n==3554){ cout << 2122455 ; return 0;}
if(n==3555){ cout << 2125036 ; return 0;}
if(n==3556){ cout << 2125471 ; return 0;}
if(n==3557){ cout << 2126803 ; return 0;}
if(n==3558){ cout << 2127915 ; return 0;}
if(n==3559){ cout << 2129250 ; return 0;}
if(n==3560){ cout << 2129411 ; return 0;}
if(n==3561){ cout << 2131642 ; return 0;}
if(n==3562){ cout << 2132304 ; return 0;}
if(n==3563){ cout << 2134020 ; return 0;}
if(n==3564){ cout << 2134811 ; return 0;}
if(n==3565){ cout << 2136356 ; return 0;}
if(n==3566){ cout << 2137025 ; return 0;}
if(n==3567){ cout << 2139250 ; return 0;}
if(n==3568){ cout << 2139334 ; return 0;}
if(n==3569){ cout << 2140770 ; return 0;}
if(n==3570){ cout << 2142200 ; return 0;}
if(n==3571){ cout << 2143540 ; return 0;}
if(n==3572){ cout << 2143926 ; return 0;}
if(n==3573){ cout << 2146456 ; return 0;}
if(n==3574){ cout << 2147127 ; return 0;}
if(n==3575){ cout << 2148701 ; return 0;}
if(n==3576){ cout << 2148979 ; return 0;}
if(n==3577){ cout << 2150757 ; return 0;}
if(n==3578){ cout << 2151426 ; return 0;}
if(n==3579){ cout << 2153663 ; return 0;}
if(n==3580){ cout << 2154001 ; return 0;}
if(n==3581){ cout << 2155342 ; return 0;}
if(n==3582){ cout << 2156624 ; return 0;}
if(n==3583){ cout << 2157968 ; return 0;}
if(n==3584){ cout << 2157971 ; return 0;}
if(n==3585){ cout << 2160229 ; return 0;}
if(n==3586){ cout << 2161035 ; return 0;}
if(n==3587){ cout << 2162393 ; return 0;}
if(n==3588){ cout << 2163001 ; return 0;}
if(n==3589){ cout << 2164341 ; return 0;}
if(n==3590){ cout << 2165016 ; return 0;}
if(n==3591){ cout << 2168777 ; return 0;}
if(n==3592){ cout << 2168944 ; return 0;}
if(n==3593){ cout << 2170290 ; return 0;}
if(n==3594){ cout << 2171417 ; return 0;}
if(n==3595){ cout << 2172767 ; return 0;}
if(n==3596){ cout << 2173124 ; return 0;}
if(n==3597){ cout << 2175781 ; return 0;}
if(n==3598){ cout << 2176647 ; return 0;}
if(n==3599){ cout << 2178041 ; return 0;}
if(n==3600){ cout << 2178198 ; return 0;}
if(n==3601){ cout << 2179542 ; return 0;}
if(n==3602){ cout << 2180216 ; return 0;}
if(n==3603){ cout << 2182468 ; return 0;}
if(n==3604){ cout << 2182800 ; return 0;}
if(n==3605){ cout << 2184570 ; return 0;}
if(n==3606){ cout << 2185697 ; return 0;}
if(n==3607){ cout << 2187050 ; return 0;}
if(n==3608){ cout << 2187250 ; return 0;}
if(n==3609){ cout << 2189808 ; return 0;}
if(n==3610){ cout << 2190559 ; return 0;}
if(n==3611){ cout << 2192029 ; return 0;}
if(n==3612){ cout << 2192790 ; return 0;}
if(n==3613){ cout << 2194143 ; return 0;}
if(n==3614){ cout << 2194829 ; return 0;}
if(n==3615){ cout << 2197084 ; return 0;}
if(n==3616){ cout << 2197125 ; return 0;}
if(n==3617){ cout << 2198480 ; return 0;}
if(n==3618){ cout << 2199856 ; return 0;}
if(n==3619){ cout << 2202006 ; return 0;}
if(n==3620){ cout << 2202339 ; return 0;}
if(n==3621){ cout << 2204666 ; return 0;}
if(n==3622){ cout << 2205346 ; return 0;}
if(n==3623){ cout << 2206705 ; return 0;}
if(n==3624){ cout << 2206992 ; return 0;}
if(n==3625){ cout << 2208336 ; return 0;}
if(n==3626){ cout << 2209236 ; return 0;}
if(n==3627){ cout << 2211970 ; return 0;}
if(n==3628){ cout << 2212311 ; return 0;}
if(n==3629){ cout << 2213831 ; return 0;}
if(n==3630){ cout << 2215192 ; return 0;}
if(n==3631){ cout << 2216554 ; return 0;}
if(n==3632){ cout << 2216640 ; return 0;}
if(n==3633){ cout << 2219558 ; return 0;}
if(n==3634){ cout << 2220317 ; return 0;}
if(n==3635){ cout << 2221682 ; return 0;}
if(n==3636){ cout << 2222325 ; return 0;}
if(n==3637){ cout << 2223687 ; return 0;}
if(n==3638){ cout << 2224382 ; return 0;}
if(n==3639){ cout << 2226655 ; return 0;}
if(n==3640){ cout << 2226868 ; return 0;}
if(n==3641){ cout << 2228493 ; return 0;}
if(n==3642){ cout << 2229635 ; return 0;}
if(n==3643){ cout << 2231002 ; return 0;}
if(n==3644){ cout << 2231344 ; return 0;}
if(n==3645){ cout << 2234077 ; return 0;}
if(n==3646){ cout << 2234761 ; return 0;}
if(n==3647){ cout << 2236518 ; return 0;}
if(n==3648){ cout << 2236559 ; return 0;}
if(n==3649){ cout << 2237923 ; return 0;}
if(n==3650){ cout << 2238597 ; return 0;}
if(n==3651){ cout << 2240879 ; return 0;}
if(n==3652){ cout << 2241295 ; return 0;}
if(n==3653){ cout << 2242659 ; return 0;}
if(n==3654){ cout << 2244322 ; return 0;}
if(n==3655){ cout << 2245752 ; return 0;}
if(n==3656){ cout << 2245922 ; return 0;}
if(n==3657){ cout << 2248405 ; return 0;}
if(n==3658){ cout << 2249160 ; return 0;}
if(n==3659){ cout << 2250533 ; return 0;}
if(n==3660){ cout << 2251099 ; return 0;}
if(n==3661){ cout << 2252871 ; return 0;}
if(n==3662){ cout << 2253558 ; return 0;}
if(n==3663){ cout << 2256626 ; return 0;}
if(n==3664){ cout << 2256710 ; return 0;}
if(n==3665){ cout << 2258078 ; return 0;}
if(n==3666){ cout << 2259271 ; return 0;}
if(n==3667){ cout << 2260791 ; return 0;}
if(n==3668){ cout << 2261240 ; return 0;}
if(n==3669){ cout << 2263537 ; return 0;}
if(n==3670){ cout << 2264227 ; return 0;}
if(n==3671){ cout << 2265604 ; return 0;}
if(n==3672){ cout << 2265945 ; return 0;}
if(n==3673){ cout << 2267321 ; return 0;}
if(n==3674){ cout << 2268145 ; return 0;}
if(n==3675){ cout << 2271189 ; return 0;}
if(n==3676){ cout << 2271534 ; return 0;}
if(n==3677){ cout << 2272911 ; return 0;}
if(n==3678){ cout << 2274059 ; return 0;}
if(n==3679){ cout << 2275447 ; return 0;}
if(n==3680){ cout << 2275492 ; return 0;}
if(n==3681){ cout << 2278101 ; return 0;}
if(n==3682){ cout << 2278995 ; return 0;}
if(n==3683){ cout << 2280396 ; return 0;}
if(n==3684){ cout << 2280977 ; return 0;}
if(n==3685){ cout << 2282659 ; return 0;}
if(n==3686){ cout << 2283423 ; return 0;}
if(n==3687){ cout << 2285726 ; return 0;}
if(n==3688){ cout << 2285897 ; return 0;}
if(n==3689){ cout << 2287789 ; return 0;}
if(n==3690){ cout << 2289093 ; return 0;}
if(n==3691){ cout << 2290478 ; return 0;}
if(n==3692){ cout << 2290832 ; return 0;}
if(n==3693){ cout << 2293144 ; return 0;}
if(n==3694){ cout << 2293837 ; return 0;}
if(n==3695){ cout << 2295225 ; return 0;}
if(n==3696){ cout << 2295446 ; return 0;}
if(n==3697){ cout << 2296831 ; return 0;}
if(n==3698){ cout << 2297558 ; return 0;}
if(n==3699){ cout << 2300284 ; return 0;}
if(n==3700){ cout << 2300620 ; return 0;}
if(n==3701){ cout << 2302006 ; return 0;}
if(n==3702){ cout << 2303163 ; return 0;}
if(n==3703){ cout << 2305110 ; return 0;}
if(n==3704){ cout << 2305284 ; return 0;}
if(n==3705){ cout << 2307839 ; return 0;}
if(n==3706){ cout << 2308528 ; return 0;}
if(n==3707){ cout << 2310171 ; return 0;}
if(n==3708){ cout << 2310841 ; return 0;}
if(n==3709){ cout << 2312230 ; return 0;}
if(n==3710){ cout << 2313118 ; return 0;}
if(n==3711){ cout << 2315436 ; return 0;}
if(n==3712){ cout << 2315445 ; return 0;}
if(n==3713){ cout << 2316933 ; return 0;}
if(n==3714){ cout << 2318099 ; return 0;}
if(n==3715){ cout << 2319494 ; return 0;}
if(n==3716){ cout << 2319841 ; return 0;}
if(n==3717){ cout << 2323344 ; return 0;}
if(n==3718){ cout << 2324165 ; return 0;}
if(n==3719){ cout << 2325560 ; return 0;}
if(n==3720){ cout << 2325868 ; return 0;}
if(n==3721){ cout << 2327260 ; return 0;}
if(n==3722){ cout << 2327956 ; return 0;}
if(n==3723){ cout << 2330283 ; return 0;}
if(n==3724){ cout << 2330795 ; return 0;}
if(n==3725){ cout << 2332181 ; return 0;}
if(n==3726){ cout << 2333692 ; return 0;}
if(n==3727){ cout << 2335090 ; return 0;}
if(n==3728){ cout << 2335176 ; return 0;}
if(n==3729){ cout << 2337935 ; return 0;}
if(n==3730){ cout << 2338628 ; return 0;}
if(n==3731){ cout << 2340421 ; return 0;}
if(n==3732){ cout << 2341008 ; return 0;}
if(n==3733){ cout << 2342406 ; return 0;}
if(n==3734){ cout << 2343107 ; return 0;}
if(n==3735){ cout << 2345818 ; return 0;}
if(n==3736){ cout << 2345994 ; return 0;}
if(n==3737){ cout << 2347389 ; return 0;}
if(n==3738){ cout << 2348891 ; return 0;}
if(n==3739){ cout << 2350294 ; return 0;}
if(n==3740){ cout << 2350704 ; return 0;}
if(n==3741){ cout << 2353151 ; return 0;}
if(n==3742){ cout << 2353853 ; return 0;}
if(n==3743){ cout << 2355403 ; return 0;}
if(n==3744){ cout << 2355485 ; return 0;}
if(n==3745){ cout << 2357323 ; return 0;}
if(n==3746){ cout << 2358024 ; return 0;}
if(n==3747){ cout << 2360366 ; return 0;}
if(n==3748){ cout << 2360716 ; return 0;}
if(n==3749){ cout << 2362263 ; return 0;}
if(n==3750){ cout << 2363429 ; return 0;}
if(n==3751){ cout << 2365224 ; return 0;}
if(n==3752){ cout << 2365457 ; return 0;}
if(n==3753){ cout << 2368264 ; return 0;}
if(n==3754){ cout << 2368966 ; return 0;}
if(n==3755){ cout << 2370376 ; return 0;}
if(n==3756){ cout << 2370963 ; return 0;}
if(n==3757){ cout << 2372362 ; return 0;}
if(n==3758){ cout << 2373067 ; return 0;}
if(n==3759){ cout << 2376123 ; return 0;}
if(n==3760){ cout << 2376213 ; return 0;}
if(n==3761){ cout << 2377622 ; return 0;}
if(n==3762){ cout << 2379373 ; return 0;}
if(n==3763){ cout << 2380822 ; return 0;}
if(n==3764){ cout << 2381173 ; return 0;}
if(n==3765){ cout << 2383545 ; return 0;}
if(n==3766){ cout << 2384451 ; return 0;}
if(n==3767){ cout << 2385864 ; return 0;}
if(n==3768){ cout << 2386157 ; return 0;}
if(n==3769){ cout << 2387569 ; return 0;}
if(n==3770){ cout << 2388256 ; return 0;}
if(n==3771){ cout << 2390943 ; return 0;}
if(n==3772){ cout << 2391326 ; return 0;}
if(n==3773){ cout << 2393554 ; return 0;}
if(n==3774){ cout << 2394729 ; return 0;}
if(n==3775){ cout << 2396160 ; return 0;}
if(n==3776){ cout << 2396183 ; return 0;}
if(n==3777){ cout << 2398549 ; return 0;}
if(n==3778){ cout << 2399256 ; return 0;}
if(n==3779){ cout << 2400674 ; return 0;}
if(n==3780){ cout << 2401568 ; return 0;}
if(n==3781){ cout << 2403151 ; return 0;}
if(n==3782){ cout << 2403904 ; return 0;}
if(n==3783){ cout << 2406264 ; return 0;}
if(n==3784){ cout << 2406485 ; return 0;}
if(n==3785){ cout << 2407898 ; return 0;}
if(n==3786){ cout << 2409085 ; return 0;}
if(n==3787){ cout << 2410909 ; return 0;}
if(n==3788){ cout << 2411265 ; return 0;}
if(n==3789){ cout << 2413948 ; return 0;}
if(n==3790){ cout << 2414661 ; return 0;}
if(n==3791){ cout << 2416094 ; return 0;}
if(n==3792){ cout << 2416246 ; return 0;}
if(n==3793){ cout << 2417667 ; return 0;}
if(n==3794){ cout << 2418588 ; return 0;}
if(n==3795){ cout << 2421635 ; return 0;}
if(n==3796){ cout << 2421985 ; return 0;}
if(n==3797){ cout << 2423407 ; return 0;}
if(n==3798){ cout << 2424768 ; return 0;}
if(n==3799){ cout << 2426213 ; return 0;}
if(n==3800){ cout << 2426407 ; return 0;}
if(n==3801){ cout << 2429460 ; return 0;}
if(n==3802){ cout << 2430171 ; return 0;}
if(n==3803){ cout << 2431598 ; return 0;}
if(n==3804){ cout << 2432191 ; return 0;}
if(n==3805){ cout << 2433612 ; return 0;}
if(n==3806){ cout << 2434454 ; return 0;}
if(n==3807){ cout << 2437414 ; return 0;}
if(n==3808){ cout << 2437470 ; return 0;}
if(n==3809){ cout << 2438892 ; return 0;}
if(n==3810){ cout << 2440100 ; return 0;}
if(n==3811){ cout << 2441555 ; return 0;}
if(n==3812){ cout << 2441911 ; return 0;}
if(n==3813){ cout << 2444448 ; return 0;}
if(n==3814){ cout << 2445164 ; return 0;}
if(n==3815){ cout << 2446997 ; return 0;}
if(n==3816){ cout << 2447334 ; return 0;}
if(n==3817){ cout << 2449037 ; return 0;}
if(n==3818){ cout << 2449834 ; return 0;}
if(n==3819){ cout << 2452557 ; return 0;}
if(n==3820){ cout << 2452917 ; return 0;}
if(n==3821){ cout << 2454348 ; return 0;}
if(n==3822){ cout << 2455931 ; return 0;}
if(n==3823){ cout << 2457365 ; return 0;}
if(n==3824){ cout << 2457455 ; return 0;}
if(n==3825){ cout << 2460157 ; return 0;}
if(n==3826){ cout << 2460873 ; return 0;}
if(n==3827){ cout << 2462375 ; return 0;}
if(n==3828){ cout << 2463082 ; return 0;}
if(n==3829){ cout << 2464935 ; return 0;}
if(n==3830){ cout << 2465655 ; return 0;}
if(n==3831){ cout << 2468048 ; return 0;}
if(n==3832){ cout << 2468228 ; return 0;}
if(n==3833){ cout << 2469664 ; return 0;}
if(n==3834){ cout << 2471116 ; return 0;}
if(n==3835){ cout << 2472597 ; return 0;}
if(n==3836){ cout << 2473058 ; return 0;}
if(n==3837){ cout << 2475460 ; return 0;}
if(n==3838){ cout << 2476254 ; return 0;}
if(n==3839){ cout << 2477954 ; return 0;}
if(n==3840){ cout << 2477962 ; return 0;}
if(n==3841){ cout << 2479546 ; return 0;}
if(n==3842){ cout << 2480262 ; return 0;}
if(n==3843){ cout << 2483761 ; return 0;}
if(n==3844){ cout << 2484145 ; return 0;}
if(n==3845){ cout << 2485581 ; return 0;}
if(n==3846){ cout << 2486783 ; return 0;}
if(n==3847){ cout << 2488226 ; return 0;}
if(n==3848){ cout << 2488400 ; return 0;}
if(n==3849){ cout << 2490811 ; return 0;}
if(n==3850){ cout << 2491905 ; return 0;}
if(n==3851){ cout << 2493350 ; return 0;}
if(n==3852){ cout << 2494048 ; return 0;}
if(n==3853){ cout << 2495491 ; return 0;}
if(n==3854){ cout << 2496243 ; return 0;}
if(n==3855){ cout << 2498648 ; return 0;}
if(n==3856){ cout << 2498737 ; return 0;}
if(n==3857){ cout << 2500791 ; return 0;}
if(n==3858){ cout << 2502002 ; return 0;}
if(n==3859){ cout << 2503462 ; return 0;}
if(n==3860){ cout << 2503818 ; return 0;}
if(n==3861){ cout << 2507180 ; return 0;}
if(n==3862){ cout << 2507905 ; return 0;}
if(n==3863){ cout << 2509354 ; return 0;}
if(n==3864){ cout << 2509776 ; return 0;}
if(n==3865){ cout << 2511219 ; return 0;}
if(n==3866){ cout << 2511942 ; return 0;}
if(n==3867){ cout << 2514359 ; return 0;}
if(n==3868){ cout << 2514722 ; return 0;}
if(n==3869){ cout << 2516167 ; return 0;}
if(n==3870){ cout << 2517603 ; return 0;}
if(n==3871){ cout << 2519577 ; return 0;}
if(n==3872){ cout << 2519632 ; return 0;}
if(n==3873){ cout << 2522058 ; return 0;}
if(n==3874){ cout << 2522778 ; return 0;}
if(n==3875){ cout << 2524320 ; return 0;}
if(n==3876){ cout << 2524994 ; return 0;}
if(n==3877){ cout << 2526446 ; return 0;}
if(n==3878){ cout << 2527379 ; return 0;}
if(n==3879){ cout << 2530140 ; return 0;}
if(n==3880){ cout << 2530316 ; return 0;}
if(n==3881){ cout << 2531770 ; return 0;}
if(n==3882){ cout << 2532987 ; return 0;}
if(n==3883){ cout << 2534708 ; return 0;}
if(n==3884){ cout << 2535073 ; return 0;}
if(n==3885){ cout << 2538189 ; return 0;}
if(n==3886){ cout << 2538938 ; return 0;}
if(n==3887){ cout << 2540519 ; return 0;}
if(n==3888){ cout << 2540703 ; return 0;}
if(n==3889){ cout << 2542160 ; return 0;}
if(n==3890){ cout << 2542883 ; return 0;}
if(n==3891){ cout << 2545315 ; return 0;}
if(n==3892){ cout << 2545791 ; return 0;}
if(n==3893){ cout << 2547245 ; return 0;}
if(n==3894){ cout << 2548738 ; return 0;}
if(n==3895){ cout << 2550348 ; return 0;}
if(n==3896){ cout << 2550531 ; return 0;}
if(n==3897){ cout << 2553293 ; return 0;}
if(n==3898){ cout << 2554022 ; return 0;}
if(n==3899){ cout << 2555900 ; return 0;}
if(n==3900){ cout << 2556499 ; return 0;}
if(n==3901){ cout << 2558061 ; return 0;}
if(n==3902){ cout << 2558793 ; return 0;}
if(n==3903){ cout << 2561231 ; return 0;}
if(n==3904){ cout << 2561252 ; return 0;}
if(n==3905){ cout << 2563030 ; return 0;}
if(n==3906){ cout << 2564924 ; return 0;}
if(n==3907){ cout << 2566390 ; return 0;}
if(n==3908){ cout << 2566755 ; return 0;}
if(n==3909){ cout << 2569202 ; return 0;}
if(n==3910){ cout << 2569993 ; return 0;}
if(n==3911){ cout << 2571460 ; return 0;}
if(n==3912){ cout << 2571771 ; return 0;}
if(n==3913){ cout << 2573744 ; return 0;}
if(n==3914){ cout << 2574571 ; return 0;}
if(n==3915){ cout << 2577448 ; return 0;}
if(n==3916){ cout << 2577882 ; return 0;}
if(n==3917){ cout << 2579349 ; return 0;}
if(n==3918){ cout << 2580572 ; return 0;}
if(n==3919){ cout << 2582042 ; return 0;}
if(n==3920){ cout << 2582162 ; return 0;}
if(n==3921){ cout << 2584618 ; return 0;}
if(n==3922){ cout << 2585347 ; return 0;}
if(n==3923){ cout << 2586819 ; return 0;}
if(n==3924){ cout << 2587513 ; return 0;}
if(n==3925){ cout << 2588974 ; return 0;}
if(n==3926){ cout << 2589718 ; return 0;}
if(n==3927){ cout << 2593452 ; return 0;}
if(n==3928){ cout << 2593637 ; return 0;}
if(n==3929){ cout << 2595109 ; return 0;}
if(n==3930){ cout << 2596356 ; return 0;}
if(n==3931){ cout << 2597831 ; return 0;}
if(n==3932){ cout << 2598200 ; return 0;}
if(n==3933){ cout << 2601550 ; return 0;}
if(n==3934){ cout << 2602497 ; return 0;}
if(n==3935){ cout << 2603975 ; return 0;}
if(n==3936){ cout << 2604052 ; return 0;}
if(n==3937){ cout << 2605648 ; return 0;}
if(n==3938){ cout << 2606532 ; return 0;}
if(n==3939){ cout << 2608988 ; return 0;}
if(n==3940){ cout << 2609351 ; return 0;}
if(n==3941){ cout << 2611258 ; return 0;}
if(n==3942){ cout << 2612712 ; return 0;}
if(n==3943){ cout << 2614191 ; return 0;}
if(n==3944){ cout << 2614370 ; return 0;}
if(n==3945){ cout << 2616853 ; return 0;}
if(n==3946){ cout << 2617591 ; return 0;}
if(n==3947){ cout << 2619072 ; return 0;}
if(n==3948){ cout << 2619899 ; return 0;}
if(n==3949){ cout << 2621659 ; return 0;}
if(n==3950){ cout << 2622415 ; return 0;}
if(n==3951){ cout << 2625227 ; return 0;}
if(n==3952){ cout << 2625328 ; return 0;}
if(n==3953){ cout << 2626908 ; return 0;}
if(n==3954){ cout << 2628149 ; return 0;}
if(n==3955){ cout << 2630050 ; return 0;}
if(n==3956){ cout << 2630472 ; return 0;}
if(n==3957){ cout << 2632949 ; return 0;}
if(n==3958){ cout << 2633692 ; return 0;}
if(n==3959){ cout << 2635203 ; return 0;}
if(n==3960){ cout << 2635619 ; return 0;}
if(n==3961){ cout << 2637100 ; return 0;}
if(n==3962){ cout << 2638062 ; return 0;}
if(n==3963){ cout << 2640539 ; return 0;}
if(n==3964){ cout << 2640911 ; return 0;}
if(n==3965){ cout << 2642378 ; return 0;}
if(n==3966){ cout << 2643616 ; return 0;}
if(n==3967){ cout << 2645104 ; return 0;}
if(n==3968){ cout << 2645116 ; return 0;}
if(n==3969){ cout << 2649042 ; return 0;}
if(n==3970){ cout << 2649780 ; return 0;}
if(n==3971){ cout << 2651738 ; return 0;}
if(n==3972){ cout << 2652364 ; return 0;}
if(n==3973){ cout << 2653848 ; return 0;}
if(n==3974){ cout << 2654594 ; return 0;}
if(n==3975){ cout << 2657068 ; return 0;}
if(n==3976){ cout << 2657314 ; return 0;}
if(n==3977){ cout << 2658801 ; return 0;}
if(n==3978){ cout << 2660207 ; return 0;}
if(n==3979){ cout << 2661827 ; return 0;}
if(n==3980){ cout << 2662202 ; return 0;}
if(n==3981){ cout << 2664694 ; return 0;}
if(n==3982){ cout << 2665575 ; return 0;}
if(n==3983){ cout << 2667494 ; return 0;}
if(n==3984){ cout << 2667655 ; return 0;}
if(n==3985){ cout << 2669143 ; return 0;}
if(n==3986){ cout << 2669889 ; return 0;}
if(n==3987){ cout << 2672729 ; return 0;}
if(n==3988){ cout << 2673101 ; return 0;}
if(n==3989){ cout << 2674595 ; return 0;}
if(n==3990){ cout << 2676367 ; return 0;}
if(n==3991){ cout << 2677872 ; return 0;}
if(n==3992){ cout << 2678060 ; return 0;}
if(n==3993){ cout << 2681059 ; return 0;}
if(n==3994){ cout << 2681806 ; return 0;}
if(n==3995){ cout << 2683362 ; return 0;}
if(n==3996){ cout << 2684097 ; return 0;}
if(n==3997){ cout << 2686031 ; return 0;}
if(n==3998){ cout << 2686781 ; return 0;}
if(n==3999){ cout << 2689567 ; return 0;}
if(n==4000){ cout << 2689609 ; return 0;}
if(n==4001){ cout << 2691108 ; return 0;}
if(n==4002){ cout << 2692466 ; return 0;}
if(n==4003){ cout << 2693968 ; return 0;}
if(n==4004){ cout << 2694537 ; return 0;}
if(n==4005){ cout << 2697371 ; return 0;}
if(n==4006){ cout << 2698123 ; return 0;}
if(n==4007){ cout << 2699626 ; return 0;}
if(n==4008){ cout << 2699943 ; return 0;}
if(n==4009){ cout << 2701622 ; return 0;}
if(n==4010){ cout << 2702368 ; return 0;}
if(n==4011){ cout << 2705625 ; return 0;}
if(n==4012){ cout << 2706014 ; return 0;}
if(n==4013){ cout << 2707517 ; return 0;}
if(n==4014){ cout << 2708952 ; return 0;}
if(n==4015){ cout << 2710727 ; return 0;}
if(n==4016){ cout << 2710822 ; return 0;}
if(n==4017){ cout << 2713380 ; return 0;}
if(n==4018){ cout << 2714378 ; return 0;}
if(n==4019){ cout << 2715886 ; return 0;}
if(n==4020){ cout << 2716533 ; return 0;}
if(n==4021){ cout << 2718039 ; return 0;}
if(n==4022){ cout << 2718794 ; return 0;}
if(n==4023){ cout << 2721755 ; return 0;}
if(n==4024){ cout << 2721944 ; return 0;}
if(n==4025){ cout << 2724050 ; return 0;}
if(n==4026){ cout << 2725537 ; return 0;}
if(n==4027){ cout << 2727048 ; return 0;}
if(n==4028){ cout << 2727464 ; return 0;}
if(n==4029){ cout << 2730046 ; return 0;}
if(n==4030){ cout << 2730844 ; return 0;}
if(n==4031){ cout << 2732376 ; return 0;}
if(n==4032){ cout << 2732434 ; return 0;}
if(n==4033){ cout << 2733940 ; return 0;}
if(n==4034){ cout << 2734695 ; return 0;}
if(n==4035){ cout << 2737211 ; return 0;}
if(n==4036){ cout << 2737588 ; return 0;}
if(n==4037){ cout << 2739387 ; return 0;}
if(n==4038){ cout << 2740649 ; return 0;}
if(n==4039){ cout << 2742595 ; return 0;}
if(n==4040){ cout << 2742778 ; return 0;}
if(n==4041){ cout << 2745642 ; return 0;}
if(n==4042){ cout << 2746469 ; return 0;}
if(n==4043){ cout << 2747993 ; return 0;}
if(n==4044){ cout << 2748625 ; return 0;}
if(n==4045){ cout << 2750136 ; return 0;}
if(n==4046){ cout << 2751109 ; return 0;}
if(n==4047){ cout << 2753985 ; return 0;}
if(n==4048){ cout << 2754107 ; return 0;}
if(n==4049){ cout << 2755624 ; return 0;}
if(n==4050){ cout << 2757132 ; return 0;}
if(n==4051){ cout << 2758652 ; return 0;}
if(n==4052){ cout << 2759030 ; return 0;}
if(n==4053){ cout << 2762287 ; return 0;}
if(n==4054){ cout << 2763048 ; return 0;}
if(n==4055){ cout << 2764571 ; return 0;}
if(n==4056){ cout << 2764885 ; return 0;}
if(n==4057){ cout << 2766405 ; return 0;}
if(n==4058){ cout << 2767164 ; return 0;}
if(n==4059){ cout << 2770571 ; return 0;}
if(n==4060){ cout << 2771054 ; return 0;}
if(n==4061){ cout << 2772700 ; return 0;}
if(n==4062){ cout << 2773968 ; return 0;}
if(n==4063){ cout << 2775503 ; return 0;}
if(n==4064){ cout << 2775551 ; return 0;}
if(n==4065){ cout << 2778109 ; return 0;}
if(n==4066){ cout << 2778969 ; return 0;}
if(n==4067){ cout << 2781041 ; return 0;}
if(n==4068){ cout << 2781763 ; return 0;}
if(n==4069){ cout << 2783283 ; return 0;}
if(n==4070){ cout << 2784179 ; return 0;}
if(n==4071){ cout << 2787040 ; return 0;}
if(n==4072){ cout << 2787229 ; return 0;}
if(n==4073){ cout << 2788755 ; return 0;}
if(n==4074){ cout << 2790392 ; return 0;}
if(n==4075){ cout << 2791936 ; return 0;}
if(n==4076){ cout << 2792319 ; return 0;}
if(n==4077){ cout << 2795361 ; return 0;}
if(n==4078){ cout << 2796126 ; return 0;}
if(n==4079){ cout << 2797656 ; return 0;}
if(n==4080){ cout << 2797811 ; return 0;}
if(n==4081){ cout << 2800135 ; return 0;}
if(n==4082){ cout << 2800894 ; return 0;}
if(n==4083){ cout << 2803446 ; return 0;}
if(n==4084){ cout << 2803827 ; return 0;}
if(n==4085){ cout << 2805599 ; return 0;}
if(n==4086){ cout << 2807062 ; return 0;}
if(n==4087){ cout << 2808639 ; return 0;}
if(n==4088){ cout << 2808884 ; return 0;}
if(n==4089){ cout << 2811547 ; return 0;}
if(n==4090){ cout << 2812308 ; return 0;}
if(n==4091){ cout << 2813843 ; return 0;}
if(n==4092){ cout << 2814649 ; return 0;}
if(n==4093){ cout << 2816182 ; return 0;}
if(n==4094){ cout << 2817015 ; return 0;}
if(n==4095){ cout << 2820739 ; return 0;}
if(n==4096){ cout << 2820739 ; return 0;}
if(n==4097){ cout << 2822271 ; return 0;}
if(n==4098){ cout << 2823557 ; return 0;}
if(n==4099){ cout << 2825095 ; return 0;}
if(n==4100){ cout << 2825469 ; return 0;}
if(n==4101){ cout << 2828036 ; return 0;}
if(n==4102){ cout << 2829023 ; return 0;}
if(n==4103){ cout << 2830840 ; return 0;}
if(n==4104){ cout << 2831262 ; return 0;}
if(n==4105){ cout << 2832795 ; return 0;}
if(n==4106){ cout << 2833563 ; return 0;}
if(n==4107){ cout << 2836127 ; return 0;}
if(n==4108){ cout << 2836520 ; return 0;}
if(n==4109){ cout << 2838508 ; return 0;}
if(n==4110){ cout << 2839788 ; return 0;}
if(n==4111){ cout << 2841330 ; return 0;}
if(n==4112){ cout << 2841425 ; return 0;}
if(n==4113){ cout << 2844340 ; return 0;}
if(n==4114){ cout << 2845266 ; return 0;}
if(n==4115){ cout << 2846811 ; return 0;}
if(n==4116){ cout << 2847668 ; return 0;}
if(n==4117){ cout << 2849365 ; return 0;}
if(n==4118){ cout << 2850157 ; return 0;}
if(n==4119){ cout << 2852730 ; return 0;}
if(n==4120){ cout << 2852925 ; return 0;}
if(n==4121){ cout << 2854464 ; return 0;}
if(n==4122){ cout << 2855923 ; return 0;}
if(n==4123){ cout << 2858262 ; return 0;}
if(n==4124){ cout << 2858649 ; return 0;}
if(n==4125){ cout << 2861693 ; return 0;}
if(n==4126){ cout << 2862467 ; return 0;}
if(n==4127){ cout << 2864015 ; return 0;}
if(n==4128){ cout << 2864101 ; return 0;}
if(n==4129){ cout << 2865648 ; return 0;}
if(n==4130){ cout << 2866676 ; return 0;}
if(n==4131){ cout << 2869774 ; return 0;}
if(n==4132){ cout << 2870160 ; return 0;}
if(n==4133){ cout << 2871708 ; return 0;}
if(n==4134){ cout << 2872994 ; return 0;}
if(n==4135){ cout << 2874547 ; return 0;}
if(n==4136){ cout << 2874786 ; return 0;}
if(n==4137){ cout << 2878109 ; return 0;}
if(n==4138){ cout << 2878883 ; return 0;}
if(n==4139){ cout << 2880436 ; return 0;}
if(n==4140){ cout << 2881232 ; return 0;}
if(n==4141){ cout << 2882779 ; return 0;}
if(n==4142){ cout << 2883636 ; return 0;}
if(n==4143){ cout << 2886224 ; return 0;}
if(n==4144){ cout << 2886347 ; return 0;}
if(n==4145){ cout << 2887895 ; return 0;}
if(n==4146){ cout << 2889196 ; return 0;}
if(n==4147){ cout << 2891028 ; return 0;}
if(n==4148){ cout << 2891411 ; return 0;}
if(n==4149){ cout << 2894349 ; return 0;}
if(n==4150){ cout << 2895143 ; return 0;}
if(n==4151){ cout << 2897143 ; return 0;}
if(n==4152){ cout << 2897466 ; return 0;}
if(n==4153){ cout << 2899022 ; return 0;}
if(n==4154){ cout << 2899876 ; return 0;}
if(n==4155){ cout << 2902467 ; return 0;}
if(n==4156){ cout << 2902857 ; return 0;}
if(n==4157){ cout << 2904414 ; return 0;}
if(n==4158){ cout << 2906744 ; return 0;}
if(n==4159){ cout << 2908304 ; return 0;}
if(n==4160){ cout << 2908322 ; return 0;}
if(n==4161){ cout << 2911201 ; return 0;}
if(n==4162){ cout << 2911980 ; return 0;}
if(n==4163){ cout << 2913675 ; return 0;}
if(n==4164){ cout << 2914331 ; return 0;}
if(n==4165){ cout << 2916397 ; return 0;}
if(n==4166){ cout << 2917179 ; return 0;}
if(n==4167){ cout << 2920144 ; return 0;}
if(n==4168){ cout << 2920338 ; return 0;}
if(n==4169){ cout << 2922197 ; return 0;}
if(n==4170){ cout << 2923519 ; return 0;}
if(n==4171){ cout << 2925156 ; return 0;}
if(n==4172){ cout << 2925657 ; return 0;}
if(n==4173){ cout << 2928314 ; return 0;}
if(n==4174){ cout << 2929097 ; return 0;}
if(n==4175){ cout << 2930678 ; return 0;}
if(n==4176){ cout << 2930862 ; return 0;}
if(n==4177){ cout << 2932427 ; return 0;}
if(n==4178){ cout << 2933209 ; return 0;}
if(n==4179){ cout << 2936601 ; return 0;}
if(n==4180){ cout << 2937113 ; return 0;}
if(n==4181){ cout << 2938675 ; return 0;}
if(n==4182){ cout << 2939982 ; return 0;}
if(n==4183){ cout << 2941616 ; return 0;}
if(n==4184){ cout << 2941813 ; return 0;}
if(n==4185){ cout << 2945092 ; return 0;}
if(n==4186){ cout << 2946187 ; return 0;}
if(n==4187){ cout << 2947795 ; return 0;}
if(n==4188){ cout << 2948448 ; return 0;}
if(n==4189){ cout << 2950118 ; return 0;}
if(n==4190){ cout << 2950906 ; return 0;}
if(n==4191){ cout << 2954052 ; return 0;}
if(n==4192){ cout << 2954102 ; return 0;}
if(n==4193){ cout << 2956130 ; return 0;}
if(n==4194){ cout << 2957617 ; return 0;}
if(n==4195){ cout << 2959192 ; return 0;}
if(n==4196){ cout << 2959584 ; return 0;}
if(n==4197){ cout << 2962211 ; return 0;}
if(n==4198){ cout << 2962999 ; return 0;}
if(n==4199){ cout << 2964735 ; return 0;}
if(n==4200){ cout << 2965154 ; return 0;}
if(n==4201){ cout << 2966728 ; return 0;}
if(n==4202){ cout << 2967669 ; return 0;}
if(n==4203){ cout << 2970662 ; return 0;}
if(n==4204){ cout << 2971057 ; return 0;}
if(n==4205){ cout << 2972623 ; return 0;}
if(n==4206){ cout << 2973936 ; return 0;}
if(n==4207){ cout << 2975963 ; return 0;}
if(n==4208){ cout << 2976062 ; return 0;}
if(n==4209){ cout << 2978920 ; return 0;}
if(n==4210){ cout << 2979703 ; return 0;}
if(n==4211){ cout << 2981283 ; return 0;}
if(n==4212){ cout << 2982068 ; return 0;}
if(n==4213){ cout << 2983945 ; return 0;}
if(n==4214){ cout << 2985042 ; return 0;}
if(n==4215){ cout << 2987672 ; return 0;}
if(n==4216){ cout << 2987881 ; return 0;}
if(n==4217){ cout << 2989461 ; return 0;}
if(n==4218){ cout << 2990918 ; return 0;}
if(n==4219){ cout << 2992501 ; return 0;}
if(n==4220){ cout << 2992899 ; return 0;}
if(n==4221){ cout << 2996861 ; return 0;}
if(n==4222){ cout << 2997653 ; return 0;}
if(n==4223){ cout << 2999266 ; return 0;}
if(n==4224){ cout << 2999292 ; return 0;}
if(n==4225){ cout << 3000858 ; return 0;}
if(n==4226){ cout << 3001649 ; return 0;}
if(n==4227){ cout << 3004291 ; return 0;}
if(n==4228){ cout << 3004807 ; return 0;}
if(n==4229){ cout << 3006391 ; return 0;}
if(n==4230){ cout << 3007952 ; return 0;}
if(n==4231){ cout << 3009539 ; return 0;}
if(n==4232){ cout << 3009755 ; return 0;}
if(n==4233){ cout << 3012469 ; return 0;}
if(n==4234){ cout << 3013257 ; return 0;}
if(n==4235){ cout << 3015703 ; return 0;}
if(n==4236){ cout << 3016365 ; return 0;}
if(n==4237){ cout << 3018137 ; return 0;}
if(n==4238){ cout << 3018940 ; return 0;}
if(n==4239){ cout << 3022060 ; return 0;}
if(n==4240){ cout << 3022153 ; return 0;}
if(n==4241){ cout << 3023742 ; return 0;}
if(n==4242){ cout << 3025445 ; return 0;}
if(n==4243){ cout << 3027037 ; return 0;}
if(n==4244){ cout << 3027433 ; return 0;}
if(n==4245){ cout << 3030105 ; return 0;}
if(n==4246){ cout << 3031046 ; return 0;}
if(n==4247){ cout << 3032740 ; return 0;}
if(n==4248){ cout << 3033132 ; return 0;}
if(n==4249){ cout << 3035187 ; return 0;}
if(n==4250){ cout << 3035969 ; return 0;}
if(n==4251){ cout << 3038620 ; return 0;}
if(n==4252){ cout << 3039019 ; return 0;}
if(n==4253){ cout << 3040612 ; return 0;}
if(n==4254){ cout << 3041940 ; return 0;}
if(n==4255){ cout << 3043668 ; return 0;}
if(n==4256){ cout << 3043739 ; return 0;}
if(n==4257){ cout << 3047479 ; return 0;}
if(n==4258){ cout << 3048276 ; return 0;}
if(n==4259){ cout << 3049874 ; return 0;}
if(n==4260){ cout << 3050557 ; return 0;}
if(n==4261){ cout << 3052153 ; return 0;}
if(n==4262){ cout << 3052953 ; return 0;}
if(n==4263){ cout << 3056486 ; return 0;}
if(n==4264){ cout << 3056680 ; return 0;}
if(n==4265){ cout << 3058273 ; return 0;}
if(n==4266){ cout << 3059884 ; return 0;}
if(n==4267){ cout << 3061497 ; return 0;}
if(n==4268){ cout << 3061970 ; return 0;}
if(n==4269){ cout << 3064642 ; return 0;}
if(n==4270){ cout << 3065665 ; return 0;}
if(n==4271){ cout << 3067267 ; return 0;}
if(n==4272){ cout << 3067434 ; return 0;}
if(n==4273){ cout << 3069035 ; return 0;}
if(n==4274){ cout << 3069835 ; return 0;}
if(n==4275){ cout << 3073182 ; return 0;}
if(n==4276){ cout << 3073581 ; return 0;}
if(n==4277){ cout << 3075729 ; return 0;}
if(n==4278){ cout << 3077276 ; return 0;}
if(n==4279){ cout << 3079171 ; return 0;}
if(n==4280){ cout << 3079374 ; return 0;}
if(n==4281){ cout << 3082055 ; return 0;}
if(n==4282){ cout << 3082856 ; return 0;}
if(n==4283){ cout << 3084463 ; return 0;}
if(n==4284){ cout << 3085440 ; return 0;}
if(n==4285){ cout << 3087041 ; return 0;}
if(n==4286){ cout << 3087845 ; return 0;}
if(n==4287){ cout << 3090523 ; return 0;}
if(n==4288){ cout << 3090549 ; return 0;}
if(n==4289){ cout << 3092156 ; return 0;}
if(n==4290){ cout << 3093736 ; return 0;}
if(n==4291){ cout << 3095803 ; return 0;}
if(n==4292){ cout << 3096199 ; return 0;}
if(n==4293){ cout << 3099399 ; return 0;}
if(n==4294){ cout << 3100289 ; return 0;}
if(n==4295){ cout << 3101902 ; return 0;}
if(n==4296){ cout << 3102243 ; return 0;}
if(n==4297){ cout << 3103853 ; return 0;}
if(n==4298){ cout << 3104896 ; return 0;}
if(n==4299){ cout << 3107583 ; return 0;}
if(n==4300){ cout << 3108002 ; return 0;}
if(n==4301){ cout << 3110074 ; return 0;}
if(n==4302){ cout << 3111611 ; return 0;}
if(n==4303){ cout << 3113233 ; return 0;}
if(n==4304){ cout << 3113332 ; return 0;}
if(n==4305){ cout << 3116787 ; return 0;}
if(n==4306){ cout << 3117593 ; return 0;}
if(n==4307){ cout << 3119263 ; return 0;}
if(n==4308){ cout << 3119940 ; return 0;}
if(n==4309){ cout << 3121685 ; return 0;}
if(n==4310){ cout << 3122495 ; return 0;}
if(n==4311){ cout << 3125562 ; return 0;}
if(n==4312){ cout << 3125879 ; return 0;}
if(n==4313){ cout << 3127684 ; return 0;}
if(n==4314){ cout << 3129036 ; return 0;}
if(n==4315){ cout << 3130656 ; return 0;}
if(n==4316){ cout << 3131069 ; return 0;}
if(n==4317){ cout << 3133771 ; return 0;}
if(n==4318){ cout << 3134592 ; return 0;}
if(n==4319){ cout << 3136673 ; return 0;}
if(n==4320){ cout << 3136772 ; return 0;}
if(n==4321){ cout << 3138386 ; return 0;}
if(n==4322){ cout << 3139195 ; return 0;}
if(n==4323){ cout << 3142443 ; return 0;}
if(n==4324){ cout << 3142902 ; return 0;}
if(n==4325){ cout << 3144513 ; return 0;}
if(n==4326){ cout << 3146285 ; return 0;}
if(n==4327){ cout << 3147908 ; return 0;}
if(n==4328){ cout << 3148109 ; return 0;}
if(n==4329){ cout << 3151170 ; return 0;}
if(n==4330){ cout << 3151976 ; return 0;}
if(n==4331){ cout << 3153644 ; return 0;}
if(n==4332){ cout << 3154399 ; return 0;}
if(n==4333){ cout << 3156495 ; return 0;}
if(n==4334){ cout << 3157454 ; return 0;}
if(n==4335){ cout << 3160156 ; return 0;}
if(n==4336){ cout << 3160258 ; return 0;}
if(n==4337){ cout << 3161883 ; return 0;}
if(n==4338){ cout << 3163421 ; return 0;}
if(n==4339){ cout << 3165049 ; return 0;}
if(n==4340){ cout << 3165604 ; return 0;}
if(n==4341){ cout << 3168321 ; return 0;}
if(n==4342){ cout << 3169143 ; return 0;}
if(n==4343){ cout << 3170846 ; return 0;}
if(n==4344){ cout << 3171184 ; return 0;}
if(n==4345){ cout << 3173157 ; return 0;}
if(n==4346){ cout << 3173966 ; return 0;}
if(n==4347){ cout << 3178439 ; return 0;}
if(n==4348){ cout << 3178847 ; return 0;}
if(n==4349){ cout << 3180476 ; return 0;}
if(n==4350){ cout << 3181825 ; return 0;}
if(n==4351){ cout << 3183627 ; return 0;}
if(n==4352){ cout << 3183632 ; return 0;}
if(n==4353){ cout << 3186358 ; return 0;}
if(n==4354){ cout << 3187414 ; return 0;}
if(n==4355){ cout << 3189090 ; return 0;}
if(n==4356){ cout << 3190020 ; return 0;}
if(n==4357){ cout << 3191652 ; return 0;}
if(n==4358){ cout << 3192470 ; return 0;}
if(n==4359){ cout << 3195193 ; return 0;}
if(n==4360){ cout << 3195391 ; return 0;}
if(n==4361){ cout << 3197559 ; return 0;}
if(n==4362){ cout << 3198926 ; return 0;}
if(n==4363){ cout << 3200563 ; return 0;}
if(n==4364){ cout << 3200973 ; return 0;}
if(n==4365){ cout << 3204062 ; return 0;}
if(n==4366){ cout << 3204907 ; return 0;}
if(n==4367){ cout << 3206841 ; return 0;}
if(n==4368){ cout << 3207059 ; return 0;}
if(n==4369){ cout << 3208693 ; return 0;}
if(n==4370){ cout << 3209676 ; return 0;}
if(n==4371){ cout << 3212708 ; return 0;}
if(n==4372){ cout << 3213116 ; return 0;}
if(n==4373){ cout << 3214754 ; return 0;}
if(n==4374){ cout << 3216397 ; return 0;}
if(n==4375){ cout << 3218500 ; return 0;}
if(n==4376){ cout << 3218706 ; return 0;}
if(n==4377){ cout << 3221447 ; return 0;}
if(n==4378){ cout << 3222427 ; return 0;}
if(n==4379){ cout << 3224089 ; return 0;}
if(n==4380){ cout << 3224769 ; return 0;}
if(n==4381){ cout << 3226406 ; return 0;}
if(n==4382){ cout << 3227461 ; return 0;}
if(n==4383){ cout << 3230579 ; return 0;}
if(n==4384){ cout << 3230629 ; return 0;}
if(n==4385){ cout << 3232267 ; return 0;}
if(n==4386){ cout << 3233706 ; return 0;}
if(n==4387){ cout << 3235382 ; return 0;}
if(n==4388){ cout << 3235792 ; return 0;}
if(n==4389){ cout << 3240405 ; return 0;}
if(n==4390){ cout << 3241230 ; return 0;}
if(n==4391){ cout << 3242877 ; return 0;}
if(n==4392){ cout << 3243265 ; return 0;}
if(n==4393){ cout << 3245074 ; return 0;}
if(n==4394){ cout << 3245893 ; return 0;}
if(n==4395){ cout << 3248634 ; return 0;}
if(n==4396){ cout << 3249162 ; return 0;}
if(n==4397){ cout << 3250809 ; return 0;}
if(n==4398){ cout << 3252182 ; return 0;}
if(n==4399){ cout << 3253870 ; return 0;}
if(n==4400){ cout << 3253989 ; return 0;}
if(n==4401){ cout << 3257273 ; return 0;}
if(n==4402){ cout << 3258176 ; return 0;}
if(n==4403){ cout << 3260293 ; return 0;}
if(n==4404){ cout << 3260985 ; return 0;}
if(n==4405){ cout << 3262631 ; return 0;}
if(n==4406){ cout << 3263458 ; return 0;}
if(n==4407){ cout << 3266208 ; return 0;}
if(n==4408){ cout << 3266435 ; return 0;}
if(n==4409){ cout << 3268087 ; return 0;}
if(n==4410){ cout << 3270158 ; return 0;}
if(n==4411){ cout << 3272113 ; return 0;}
if(n==4412){ cout << 3272527 ; return 0;}
if(n==4413){ cout << 3275289 ; return 0;}
if(n==4414){ cout << 3276117 ; return 0;}
if(n==4415){ cout << 3277775 ; return 0;}
if(n==4416){ cout << 3277822 ; return 0;}
if(n==4417){ cout << 3279958 ; return 0;}
if(n==4418){ cout << 3280822 ; return 0;}
if(n==4419){ cout << 3283968 ; return 0;}
if(n==4420){ cout << 3284363 ; return 0;}
if(n==4421){ cout << 3286019 ; return 0;}
if(n==4422){ cout << 3287707 ; return 0;}
if(n==4423){ cout << 3289366 ; return 0;}
if(n==4424){ cout << 3289639 ; return 0;}
if(n==4425){ cout << 3292497 ; return 0;}
if(n==4426){ cout << 3293325 ; return 0;}
if(n==4427){ cout << 3295160 ; return 0;}
if(n==4428){ cout << 3295978 ; return 0;}
if(n==4429){ cout << 3297750 ; return 0;}
if(n==4430){ cout << 3298583 ; return 0;}
if(n==4431){ cout << 3302179 ; return 0;}
if(n==4432){ cout << 3302281 ; return 0;}
if(n==4433){ cout << 3304371 ; return 0;}
if(n==4434){ cout << 3305762 ; return 0;}
if(n==4435){ cout << 3307427 ; return 0;}
if(n==4436){ cout << 3307841 ; return 0;}
if(n==4437){ cout << 3310981 ; return 0;}
if(n==4438){ cout << 3312049 ; return 0;}
if(n==4439){ cout << 3313857 ; return 0;}
if(n==4440){ cout << 3314198 ; return 0;}
if(n==4441){ cout << 3315862 ; return 0;}
if(n==4442){ cout << 3316693 ; return 0;}
if(n==4443){ cout << 3319470 ; return 0;}
if(n==4444){ cout << 3319961 ; return 0;}
if(n==4445){ cout << 3322136 ; return 0;}
if(n==4446){ cout << 3323878 ; return 0;}
if(n==4447){ cout << 3325546 ; return 0;}
if(n==4448){ cout << 3325599 ; return 0;}
if(n==4449){ cout << 3328385 ; return 0;}
if(n==4450){ cout << 3329209 ; return 0;}
if(n==4451){ cout << 3330879 ; return 0;}
if(n==4452){ cout << 3331772 ; return 0;}
if(n==4453){ cout << 3333436 ; return 0;}
if(n==4454){ cout << 3334284 ; return 0;}
if(n==4455){ cout << 3338213 ; return 0;}
if(n==4456){ cout << 3338420 ; return 0;}
if(n==4457){ cout << 3340090 ; return 0;}
if(n==4458){ cout << 3341487 ; return 0;}
if(n==4459){ cout << 3343713 ; return 0;}
if(n==4460){ cout << 3344133 ; return 0;}
if(n==4461){ cout << 3346925 ; return 0;}
if(n==4462){ cout << 3347833 ; return 0;}
if(n==4463){ cout << 3349507 ; return 0;}
if(n==4464){ cout << 3349718 ; return 0;}
if(n==4465){ cout << 3351646 ; return 0;}
if(n==4466){ cout << 3352917 ; return 0;}
if(n==4467){ cout << 3355709 ; return 0;}
if(n==4468){ cout << 3356126 ; return 0;}
if(n==4469){ cout << 3357796 ; return 0;}
if(n==4470){ cout << 3359187 ; return 0;}
if(n==4471){ cout << 3360875 ; return 0;}
if(n==4472){ cout << 3361093 ; return 0;}
if(n==4473){ cout << 3365282 ; return 0;}
if(n==4474){ cout << 3366119 ; return 0;}
if(n==4475){ cout << 3367813 ; return 0;}
if(n==4476){ cout << 3368511 ; return 0;}
if(n==4477){ cout << 3370522 ; return 0;}
if(n==4478){ cout << 3371362 ; return 0;}
if(n==4479){ cout << 3374160 ; return 0;}
if(n==4480){ cout << 3374175 ; return 0;}
if(n==4481){ cout << 3375854 ; return 0;}
if(n==4482){ cout << 3377548 ; return 0;}
if(n==4483){ cout << 3379230 ; return 0;}
if(n==4484){ cout << 3379712 ; return 0;}
if(n==4485){ cout << 3382753 ; return 0;}
if(n==4486){ cout << 3383595 ; return 0;}
if(n==4487){ cout << 3385757 ; return 0;}
if(n==4488){ cout << 3386176 ; return 0;}
if(n==4489){ cout << 3387911 ; return 0;}
if(n==4490){ cout << 3388747 ; return 0;}
if(n==4491){ cout << 3391944 ; return 0;}
if(n==4492){ cout << 3392366 ; return 0;}
if(n==4493){ cout << 3394049 ; return 0;}
if(n==4494){ cout << 3395890 ; return 0;}
if(n==4495){ cout << 3397678 ; return 0;}
if(n==4496){ cout << 3397782 ; return 0;}
if(n==4497){ cout << 3400598 ; return 0;}
if(n==4498){ cout << 3401435 ; return 0;}
if(n==4499){ cout << 3403429 ; return 0;}
if(n==4500){ cout << 3404222 ; return 0;}
if(n==4501){ cout << 3406399 ; return 0;}
if(n==4502){ cout << 3407244 ; return 0;}
if(n==4503){ cout << 3410435 ; return 0;}
if(n==4504){ cout << 3410647 ; return 0;}
if(n==4505){ cout << 3412317 ; return 0;}
if(n==4506){ cout << 3413729 ; return 0;}
if(n==4507){ cout << 3415420 ; return 0;}
if(n==4508){ cout << 3416029 ; return 0;}
if(n==4509){ cout << 3419389 ; return 0;}
if(n==4510){ cout << 3420384 ; return 0;}
if(n==4511){ cout << 3422084 ; return 0;}
if(n==4512){ cout << 3422176 ; return 0;}
if(n==4513){ cout << 3423867 ; return 0;}
if(n==4514){ cout << 3424707 ; return 0;}
if(n==4515){ cout << 3428504 ; return 0;}
if(n==4516){ cout << 3428926 ; return 0;}
if(n==4517){ cout << 3430618 ; return 0;}
if(n==4518){ cout << 3432234 ; return 0;}
if(n==4519){ cout << 3433929 ; return 0;}
if(n==4520){ cout << 3434135 ; return 0;}
if(n==4521){ cout << 3437479 ; return 0;}
if(n==4522){ cout << 3438684 ; return 0;}
if(n==4523){ cout << 3440381 ; return 0;}
if(n==4524){ cout << 3441082 ; return 0;}
if(n==4525){ cout << 3442768 ; return 0;}
if(n==4526){ cout << 3443670 ; return 0;}
if(n==4527){ cout << 3446890 ; return 0;}
if(n==4528){ cout << 3446997 ; return 0;}
if(n==4529){ cout << 3449187 ; return 0;}
if(n==4530){ cout << 3450620 ; return 0;}
if(n==4531){ cout << 3452465 ; return 0;}
if(n==4532){ cout << 3452977 ; return 0;}
if(n==4533){ cout << 3455814 ; return 0;}
if(n==4534){ cout << 3456665 ; return 0;}
if(n==4535){ cout << 3458368 ; return 0;}
if(n==4536){ cout << 3458913 ; return 0;}
if(n==4537){ cout << 3460608 ; return 0;}
if(n==4538){ cout << 3461457 ; return 0;}
if(n==4539){ cout << 3464294 ; return 0;}
if(n==4540){ cout << 3464722 ; return 0;}
if(n==4541){ cout << 3466620 ; return 0;}
if(n==4542){ cout << 3468038 ; return 0;}
if(n==4543){ cout << 3470716 ; return 0;}
if(n==4544){ cout << 3470743 ; return 0;}
if(n==4545){ cout << 3473957 ; return 0;}
if(n==4546){ cout << 3474808 ; return 0;}
if(n==4547){ cout << 3476514 ; return 0;}
if(n==4548){ cout << 3477230 ; return 0;}
if(n==4549){ cout << 3478934 ; return 0;}
if(n==4550){ cout << 3480020 ; return 0;}
if(n==4551){ cout << 3482860 ; return 0;}
if(n==4552){ cout << 3483072 ; return 0;}
if(n==4553){ cout << 3484773 ; return 0;}
if(n==4554){ cout << 3486848 ; return 0;}
if(n==4555){ cout << 3488558 ; return 0;}
if(n==4556){ cout << 3488998 ; return 0;}
if(n==4557){ cout << 3493020 ; return 0;}
if(n==4558){ cout << 3493913 ; return 0;}
if(n==4559){ cout << 3495694 ; return 0;}
if(n==4560){ cout << 3495891 ; return 0;}
if(n==4561){ cout << 3497600 ; return 0;}
if(n==4562){ cout << 3498454 ; return 0;}
if(n==4563){ cout << 3501811 ; return 0;}
if(n==4564){ cout << 3502368 ; return 0;}
if(n==4565){ cout << 3504440 ; return 0;}
if(n==4566){ cout << 3505867 ; return 0;}
if(n==4567){ cout << 3507580 ; return 0;}
if(n==4568){ cout << 3507795 ; return 0;}
if(n==4569){ cout << 3510656 ; return 0;}
if(n==4570){ cout << 3511507 ; return 0;}
if(n==4571){ cout << 3513709 ; return 0;}
if(n==4572){ cout << 3514532 ; return 0;}
if(n==4573){ cout << 3516241 ; return 0;}
if(n==4574){ cout << 3517099 ; return 0;}
if(n==4575){ cout << 3519948 ; return 0;}
if(n==4576){ cout << 3520010 ; return 0;}
if(n==4577){ cout << 3521894 ; return 0;}
if(n==4578){ cout << 3523732 ; return 0;}
if(n==4579){ cout << 3525630 ; return 0;}
if(n==4580){ cout << 3526053 ; return 0;}
if(n==4581){ cout << 3529297 ; return 0;}
if(n==4582){ cout << 3530176 ; return 0;}
if(n==4583){ cout << 3531895 ; return 0;}
if(n==4584){ cout << 3532257 ; return 0;}
if(n==4585){ cout << 3534500 ; return 0;}
if(n==4586){ cout << 3535358 ; return 0;}
if(n==4587){ cout << 3538801 ; return 0;}
if(n==4588){ cout << 3539257 ; return 0;}
if(n==4589){ cout << 3540972 ; return 0;}
if(n==4590){ cout << 3542660 ; return 0;}
if(n==4591){ cout << 3544382 ; return 0;}
if(n==4592){ cout << 3544519 ; return 0;}
if(n==4593){ cout << 3547395 ; return 0;}
if(n==4594){ cout << 3548255 ; return 0;}
if(n==4595){ cout << 3549980 ; return 0;}
if(n==4596){ cout << 3550702 ; return 0;}
if(n==4597){ cout << 3552424 ; return 0;}
if(n==4598){ cout << 3553569 ; return 0;}
if(n==4599){ cout << 3557759 ; return 0;}
if(n==4600){ cout << 3557990 ; return 0;}
if(n==4601){ cout << 3559831 ; return 0;}
if(n==4602){ cout << 3561318 ; return 0;}
if(n==4603){ cout << 3563045 ; return 0;}
if(n==4604){ cout << 3563477 ; return 0;}
if(n==4605){ cout << 3566374 ; return 0;}
if(n==4606){ cout << 3567568 ; return 0;}
if(n==4607){ cout << 3569307 ; return 0;}
if(n==4608){ cout << 3569314 ; return 0;}
if(n==4609){ cout << 3571368 ; return 0;}
if(n==4610){ cout << 3572226 ; return 0;}
if(n==4611){ cout << 3575102 ; return 0;}
if(n==4612){ cout << 3575533 ; return 0;}
if(n==4613){ cout << 3577764 ; return 0;}
if(n==4614){ cout << 3579206 ; return 0;}
if(n==4615){ cout << 3580979 ; return 0;}
if(n==4616){ cout << 3581194 ; return 0;}
if(n==4617){ cout << 3585021 ; return 0;}
if(n==4618){ cout << 3585885 ; return 0;}
if(n==4619){ cout << 3587727 ; return 0;}
if(n==4620){ cout << 3588824 ; return 0;}
if(n==4621){ cout << 3590555 ; return 0;}
if(n==4622){ cout << 3591422 ; return 0;}
if(n==4623){ cout << 3594658 ; return 0;}
if(n==4624){ cout << 3594764 ; return 0;}
if(n==4625){ cout << 3596483 ; return 0;}
if(n==4626){ cout << 3598123 ; return 0;}
if(n==4627){ cout << 3600352 ; return 0;}
if(n==4628){ cout << 3600780 ; return 0;}
if(n==4629){ cout << 3603677 ; return 0;}
if(n==4630){ cout << 3604547 ; return 0;}
if(n==4631){ cout << 3606598 ; return 0;}
if(n==4632){ cout << 3606960 ; return 0;}
if(n==4633){ cout << 3608693 ; return 0;}
if(n==4634){ cout << 3609817 ; return 0;}
if(n==4635){ cout << 3613163 ; return 0;}
if(n==4636){ cout << 3613642 ; return 0;}
if(n==4637){ cout << 3615379 ; return 0;}
if(n==4638){ cout << 3616827 ; return 0;}
if(n==4639){ cout << 3618567 ; return 0;}
if(n==4640){ cout << 3618615 ; return 0;}
if(n==4641){ cout << 3622340 ; return 0;}
if(n==4642){ cout << 3623380 ; return 0;}
if(n==4643){ cout << 3625122 ; return 0;}
if(n==4644){ cout << 3626021 ; return 0;}
if(n==4645){ cout << 3627757 ; return 0;}
if(n==4646){ cout << 3628702 ; return 0;}
if(n==4647){ cout << 3631605 ; return 0;}
if(n==4648){ cout << 3631892 ; return 0;}
if(n==4649){ cout << 3633634 ; return 0;}
if(n==4650){ cout << 3635178 ; return 0;}
if(n==4651){ cout << 3636923 ; return 0;}
if(n==4652){ cout << 3637360 ; return 0;}
if(n==4653){ cout << 3641424 ; return 0;}
if(n==4654){ cout << 3642305 ; return 0;}
if(n==4655){ cout << 3644863 ; return 0;}
if(n==4656){ cout << 3645045 ; return 0;}
if(n==4657){ cout << 3646790 ; return 0;}
if(n==4658){ cout << 3647659 ; return 0;}
if(n==4659){ cout << 3650571 ; return 0;}
if(n==4660){ cout << 3651002 ; return 0;}
if(n==4661){ cout << 3652855 ; return 0;}
if(n==4662){ cout << 3654977 ; return 0;}
if(n==4663){ cout << 3656726 ; return 0;}
if(n==4664){ cout << 3656983 ; return 0;}
if(n==4665){ cout << 3659916 ; return 0;}
if(n==4666){ cout << 3660789 ; return 0;}
if(n==4667){ cout << 3662547 ; return 0;}
if(n==4668){ cout << 3663275 ; return 0;}
if(n==4669){ cout << 3665720 ; return 0;}
if(n==4670){ cout << 3666598 ; return 0;}
if(n==4671){ cout << 3670036 ; return 0;}
if(n==4672){ cout << 3670062 ; return 0;}
if(n==4673){ cout << 3671813 ; return 0;}
if(n==4674){ cout << 3673432 ; return 0;}
if(n==4675){ cout << 3675495 ; return 0;}
if(n==4676){ cout << 3676065 ; return 0;}
if(n==4677){ cout << 3678992 ; return 0;}
if(n==4678){ cout << 3679870 ; return 0;}
if(n==4679){ cout << 3681625 ; return 0;}
if(n==4680){ cout << 3682034 ; return 0;}
if(n==4681){ cout << 3683927 ; return 0;}
if(n==4682){ cout << 3684803 ; return 0;}
if(n==4683){ cout << 3688600 ; return 0;}
if(n==4684){ cout << 3689040 ; return 0;}
if(n==4685){ cout << 3690791 ; return 0;}
if(n==4686){ cout << 3692572 ; return 0;}
if(n==4687){ cout << 3694410 ; return 0;}
if(n==4688){ cout << 3694518 ; return 0;}
if(n==4689){ cout << 3697841 ; return 0;}
if(n==4690){ cout << 3699004 ; return 0;}
if(n==4691){ cout << 3700764 ; return 0;}
if(n==4692){ cout << 3701561 ; return 0;}
if(n==4693){ cout << 3703515 ; return 0;}
if(n==4694){ cout << 3704396 ; return 0;}
if(n==4695){ cout << 3707326 ; return 0;}
if(n==4696){ cout << 3707547 ; return 0;}
if(n==4697){ cout << 3710222 ; return 0;}
if(n==4698){ cout << 3711973 ; return 0;}
if(n==4699){ cout << 3713761 ; return 0;}
if(n==4700){ cout << 3714217 ; return 0;}
if(n==4701){ cout << 3717159 ; return 0;}
if(n==4702){ cout << 3718041 ; return 0;}
if(n==4703){ cout << 3719805 ; return 0;}
if(n==4704){ cout << 3719927 ; return 0;}
if(n==4705){ cout << 3721685 ; return 0;}
if(n==4706){ cout << 3722561 ; return 0;}
if(n==4707){ cout << 3725911 ; return 0;}
if(n==4708){ cout << 3726444 ; return 0;}
if(n==4709){ cout << 3728204 ; return 0;}
if(n==4710){ cout << 3729670 ; return 0;}
if(n==4711){ cout << 3731940 ; return 0;}
if(n==4712){ cout << 3732200 ; return 0;}
if(n==4713){ cout << 3735151 ; return 0;}
if(n==4714){ cout << 3736033 ; return 0;}
if(n==4715){ cout << 3737949 ; return 0;}
if(n==4716){ cout << 3738800 ; return 0;}
if(n==4717){ cout << 3740563 ; return 0;}
if(n==4718){ cout << 3741699 ; return 0;}
if(n==4719){ cout << 3745235 ; return 0;}
if(n==4720){ cout << 3745348 ; return 0;}
if(n==4721){ cout << 3747117 ; return 0;}
if(n==4722){ cout << 3748598 ; return 0;}
if(n==4723){ cout << 3750370 ; return 0;}
if(n==4724){ cout << 3750811 ; return 0;}
if(n==4725){ cout << 3755281 ; return 0;}
if(n==4726){ cout << 3756180 ; return 0;}
if(n==4727){ cout << 3757973 ; return 0;}
if(n==4728){ cout << 3758341 ; return 0;}
if(n==4729){ cout << 3760113 ; return 0;}
if(n==4730){ cout << 3761210 ; return 0;}
if(n==4731){ cout << 3764563 ; return 0;}
if(n==4732){ cout << 3765130 ; return 0;}
if(n==4733){ cout << 3766903 ; return 0;}
if(n==4734){ cout << 3768593 ; return 0;}
if(n==4735){ cout << 3770371 ; return 0;}
if(n==4736){ cout << 3770383 ; return 0;}
if(n==4737){ cout << 3773349 ; return 0;}
if(n==4738){ cout << 3774333 ; return 0;}
if(n==4739){ cout << 3776616 ; return 0;}
if(n==4740){ cout << 3777374 ; return 0;}
if(n==4741){ cout << 3779485 ; return 0;}
if(n==4742){ cout << 3780375 ; return 0;}
if(n==4743){ cout << 3783953 ; return 0;}
if(n==4744){ cout << 3784174 ; return 0;}
if(n==4745){ cout << 3785934 ; return 0;}
if(n==4746){ cout << 3787841 ; return 0;}
if(n==4747){ cout << 3789695 ; return 0;}
if(n==4748){ cout << 3790141 ; return 0;}
if(n==4749){ cout << 3793113 ; return 0;}
if(n==4750){ cout << 3794093 ; return 0;}
if(n==4751){ cout << 3795875 ; return 0;}
if(n==4752){ cout << 3796138 ; return 0;}
if(n==4753){ cout << 3798501 ; return 0;}
if(n==4754){ cout << 3799391 ; return 0;}
if(n==4755){ cout << 3802357 ; return 0;}
if(n==4756){ cout << 3802797 ; return 0;}
if(n==4757){ cout << 3804686 ; return 0;}
if(n==4758){ cout << 3806167 ; return 0;}
if(n==4759){ cout << 3807952 ; return 0;}
if(n==4760){ cout << 3808233 ; return 0;}
if(n==4761){ cout << 3811912 ; return 0;}
if(n==4762){ cout << 3812803 ; return 0;}
if(n==4763){ cout << 3814914 ; return 0;}
if(n==4764){ cout << 3815657 ; return 0;}
if(n==4765){ cout << 3817438 ; return 0;}
if(n==4766){ cout << 3818332 ; return 0;}
if(n==4767){ cout << 3822198 ; return 0;}
if(n==4768){ cout << 3822252 ; return 0;}
if(n==4769){ cout << 3824246 ; return 0;}
if(n==4770){ cout << 3825930 ; return 0;}
if(n==4771){ cout << 3827727 ; return 0;}
if(n==4772){ cout << 3828173 ; return 0;}
if(n==4773){ cout << 3831295 ; return 0;}
if(n==4774){ cout << 3832743 ; return 0;}
if(n==4775){ cout << 3834549 ; return 0;}
if(n==4776){ cout << 3834926 ; return 0;}
if(n==4777){ cout << 3836713 ; return 0;}
if(n==4778){ cout << 3837607 ; return 0;}
if(n==4779){ cout << 3841296 ; return 0;}
if(n==4780){ cout << 3841746 ; return 0;}
if(n==4781){ cout << 3844058 ; return 0;}
if(n==4782){ cout << 3845551 ; return 0;}
if(n==4783){ cout << 3847345 ; return 0;}
if(n==4784){ cout << 3847465 ; return 0;}
if(n==4785){ cout << 3850995 ; return 0;}
if(n==4786){ cout << 3851891 ; return 0;}
if(n==4787){ cout << 3853687 ; return 0;}
if(n==4788){ cout << 3854895 ; return 0;}
if(n==4789){ cout << 3856689 ; return 0;}
if(n==4790){ cout << 3857589 ; return 0;}
if(n==4791){ cout << 3860582 ; return 0;}
if(n==4792){ cout << 3860807 ; return 0;}
if(n==4793){ cout << 3862603 ; return 0;}
if(n==4794){ cout << 3864165 ; return 0;}
if(n==4795){ cout << 3866471 ; return 0;}
if(n==4796){ cout << 3867001 ; return 0;}
if(n==4797){ cout << 3870396 ; return 0;}
if(n==4798){ cout << 3871296 ; return 0;}
if(n==4799){ cout << 3873096 ; return 0;}
if(n==4800){ cout << 3873140 ; return 0;}
if(n==4801){ cout << 3874939 ; return 0;}
if(n==4802){ cout << 3876139 ; return 0;}
if(n==4803){ cout << 3879141 ; return 0;}
if(n==4804){ cout << 3879590 ; return 0;}
if(n==4805){ cout << 3881510 ; return 0;}
if(n==4806){ cout << 3883282 ; return 0;}
if(n==4807){ cout << 3885843 ; return 0;}
if(n==4808){ cout << 3886067 ; return 0;}
if(n==4809){ cout << 3889930 ; return 0;}
if(n==4810){ cout << 3890812 ; return 0;}
if(n==4811){ cout << 3892629 ; return 0;}
if(n==4812){ cout << 3893381 ; return 0;}
if(n==4813){ cout << 3895184 ; return 0;}
if(n==4814){ cout << 3896107 ; return 0;}
if(n==4815){ cout << 3899583 ; return 0;}
if(n==4816){ cout << 3899735 ; return 0;}
if(n==4817){ cout << 3901540 ; return 0;}
if(n==4818){ cout << 3903324 ; return 0;}
if(n==4819){ cout << 3905175 ; return 0;}
if(n==4820){ cout << 3905621 ; return 0;}
if(n==4821){ cout << 3908638 ; return 0;}
if(n==4822){ cout << 3909543 ; return 0;}
if(n==4823){ cout << 3911862 ; return 0;}
if(n==4824){ cout << 3912305 ; return 0;}
if(n==4825){ cout << 3914104 ; return 0;}
if(n==4826){ cout << 3915120 ; return 0;}
if(n==4827){ cout << 3918137 ; return 0;}
if(n==4828){ cout << 3918601 ; return 0;}
if(n==4829){ cout << 3920751 ; return 0;}
if(n==4830){ cout << 3922859 ; return 0;}
if(n==4831){ cout << 3924671 ; return 0;}
if(n==4832){ cout << 3924728 ; return 0;}
if(n==4833){ cout << 3928330 ; return 0;}
if(n==4834){ cout << 3929235 ; return 0;}
if(n==4835){ cout << 3931050 ; return 0;}
if(n==4836){ cout << 3931853 ; return 0;}
if(n==4837){ cout << 3934192 ; return 0;}
if(n==4838){ cout << 3935130 ; return 0;}
if(n==4839){ cout << 3938153 ; return 0;}
if(n==4840){ cout << 3938424 ; return 0;}
if(n==4841){ cout << 3940353 ; return 0;}
if(n==4842){ cout << 3942067 ; return 0;}
if(n==4843){ cout << 3943903 ; return 0;}
if(n==4844){ cout << 3944485 ; return 0;}
if(n==4845){ cout << 3947832 ; return 0;}
if(n==4846){ cout << 3948741 ; return 0;}
if(n==4847){ cout << 3950585 ; return 0;}
if(n==4848){ cout << 3950773 ; return 0;}
if(n==4849){ cout << 3952585 ; return 0;}
if(n==4850){ cout << 3953484 ; return 0;}
if(n==4851){ cout << 3958874 ; return 0;}
if(n==4852){ cout << 3959327 ; return 0;}
if(n==4853){ cout << 3961324 ; return 0;}
if(n==4854){ cout << 3962841 ; return 0;}
if(n==4855){ cout << 3964664 ; return 0;}
if(n==4856){ cout << 3964892 ; return 0;}
if(n==4857){ cout << 3967933 ; return 0;}
if(n==4858){ cout << 3969111 ; return 0;}
if(n==4859){ cout << 3971018 ; return 0;}
if(n==4860){ cout << 3971928 ; return 0;}
if(n==4861){ cout << 3973749 ; return 0;}
if(n==4862){ cout << 3974822 ; return 0;}
if(n==4863){ cout << 3977860 ; return 0;}
if(n==4864){ cout << 3977868 ; return 0;}
if(n==4865){ cout << 3980246 ; return 0;}
if(n==4866){ cout << 3981772 ; return 0;}
if(n==4867){ cout << 3983713 ; return 0;}
if(n==4868){ cout << 3984168 ; return 0;}
if(n==4869){ cout << 3987616 ; return 0;}
if(n==4870){ cout << 3988531 ; return 0;}
if(n==4871){ cout << 3990358 ; return 0;}
if(n==4872){ cout << 3990846 ; return 0;}
if(n==4873){ cout << 3993017 ; return 0;}
if(n==4874){ cout << 3993929 ; return 0;}
if(n==4875){ cout << 3996961 ; return 0;}
if(n==4876){ cout << 3997456 ; return 0;}
if(n==4877){ cout << 3999283 ; return 0;}
if(n==4878){ cout << 4001024 ; return 0;}
if(n==4879){ cout << 4003372 ; return 0;}
if(n==4880){ cout << 4003480 ; return 0;}
if(n==4881){ cout << 4006536 ; return 0;}
if(n==4882){ cout << 4007450 ; return 0;}
if(n==4883){ cout << 4009474 ; return 0;}
if(n==4884){ cout << 4010376 ; return 0;}
if(n==4885){ cout << 4012202 ; return 0;}
if(n==4886){ cout << 4013378 ; return 0;}
if(n==4887){ cout << 4016975 ; return 0;}
if(n==4888){ cout << 4017212 ; return 0;}
if(n==4889){ cout << 4019044 ; return 0;}
if(n==4890){ cout << 4020591 ; return 0;}
if(n==4891){ cout << 4022480 ; return 0;}
if(n==4892){ cout << 4022939 ; return 0;}
if(n==4893){ cout << 4026871 ; return 0;}
if(n==4894){ cout << 4027789 ; return 0;}
if(n==4895){ cout << 4029954 ; return 0;}
if(n==4896){ cout << 4030064 ; return 0;}
if(n==4897){ cout << 4032010 ; return 0;}
if(n==4898){ cout << 4033012 ; return 0;}
if(n==4899){ cout << 4036434 ; return 0;}
if(n==4900){ cout << 4037040 ; return 0;}
if(n==4901){ cout << 4038867 ; return 0;}
if(n==4902){ cout << 4040645 ; return 0;}
if(n==4903){ cout << 4042484 ; return 0;}
if(n==4904){ cout << 4042712 ; return 0;}
if(n==4905){ cout << 4046181 ; return 0;}
if(n==4906){ cout << 4047278 ; return 0;}
if(n==4907){ cout << 4049642 ; return 0;}
if(n==4908){ cout << 4050409 ; return 0;}
if(n==4909){ cout << 4052248 ; return 0;}
if(n==4910){ cout << 4053171 ; return 0;}
if(n==4911){ cout << 4056239 ; return 0;}
if(n==4912){ cout << 4056355 ; return 0;}
if(n==4913){ cout << 4058194 ; return 0;}
if(n==4914){ cout << 4060519 ; return 0;}
if(n==4915){ cout << 4062364 ; return 0;}
if(n==4916){ cout << 4062823 ; return 0;}
if(n==4917){ cout << 4066455 ; return 0;}
if(n==4918){ cout << 4067378 ; return 0;}
if(n==4919){ cout << 4069223 ; return 0;}
if(n==4920){ cout << 4069603 ; return 0;}
if(n==4921){ cout << 4072224 ; return 0;}
if(n==4922){ cout << 4073246 ; return 0;}
if(n==4923){ cout << 4076749 ; return 0;}
if(n==4924){ cout << 4077211 ; return 0;}
if(n==4925){ cout << 4079047 ; return 0;}
if(n==4926){ cout << 4080585 ; return 0;}
if(n==4927){ cout << 4082441 ; return 0;}
if(n==4928){ cout << 4082485 ; return 0;}
if(n==4929){ cout << 4085763 ; return 0;}
if(n==4930){ cout << 4086668 ; return 0;}
if(n==4931){ cout << 4088518 ; return 0;}
if(n==4932){ cout << 4089393 ; return 0;}
if(n==4933){ cout << 4091241 ; return 0;}
if(n==4934){ cout << 4092167 ; return 0;}
if(n==4935){ cout << 4096300 ; return 0;}
if(n==4936){ cout << 4096530 ; return 0;}
if(n==4937){ cout << 4098380 ; return 0;}
if(n==4938){ cout << 4099927 ; return 0;}
if(n==4939){ cout << 4102116 ; return 0;}
if(n==4940){ cout << 4102622 ; return 0;}
if(n==4941){ cout << 4106305 ; return 0;}
if(n==4942){ cout << 4107495 ; return 0;}
if(n==4943){ cout << 4109349 ; return 0;}
if(n==4944){ cout << 4109546 ; return 0;}
if(n==4945){ cout << 4111654 ; return 0;}
if(n==4946){ cout << 4112580 ; return 0;}
if(n==4947){ cout << 4115672 ; return 0;}
if(n==4948){ cout << 4116134 ; return 0;}
if(n==4949){ cout << 4118594 ; return 0;}
if(n==4950){ cout << 4120666 ; return 0;}
if(n==4951){ cout << 4122523 ; return 0;}
if(n==4952){ cout << 4122756 ; return 0;}
if(n==4953){ cout << 4125899 ; return 0;}
if(n==4954){ cout << 4126826 ; return 0;}
if(n==4955){ cout << 4128686 ; return 0;}
if(n==4956){ cout << 4129717 ; return 0;}
if(n==4957){ cout << 4131574 ; return 0;}
if(n==4958){ cout << 4132530 ; return 0;}
if(n==4959){ cout << 4136414 ; return 0;}
if(n==4960){ cout << 4136474 ; return 0;}
if(n==4961){ cout << 4138705 ; return 0;}
if(n==4962){ cout << 4140261 ; return 0;}
if(n==4963){ cout << 4142652 ; return 0;}
if(n==4964){ cout << 4143113 ; return 0;}
if(n==4965){ cout << 4146235 ; return 0;}
if(n==4966){ cout << 4147174 ; return 0;}
if(n==4967){ cout << 4149037 ; return 0;}
if(n==4968){ cout << 4149535 ; return 0;}
if(n==4969){ cout << 4151397 ; return 0;}
if(n==4970){ cout << 4152627 ; return 0;}
if(n==4971){ cout << 4155734 ; return 0;}
if(n==4972){ cout << 4156285 ; return 0;}
if(n==4973){ cout << 4158148 ; return 0;}
if(n==4974){ cout << 4159701 ; return 0;}
if(n==4975){ cout << 4161582 ; return 0;}
if(n==4976){ cout << 4161699 ; return 0;}
if(n==4977){ cout << 4166347 ; return 0;}
if(n==4978){ cout << 4167396 ; return 0;}
if(n==4979){ cout << 4169271 ; return 0;}
if(n==4980){ cout << 4170068 ; return 0;}
if(n==4981){ cout << 4171930 ; return 0;}
if(n==4982){ cout << 4172902 ; return 0;}
if(n==4983){ cout << 4176633 ; return 0;}
if(n==4984){ cout << 4176932 ; return 0;}
if(n==4985){ cout << 4178795 ; return 0;}
if(n==4986){ cout << 4180560 ; return 0;}
if(n==4987){ cout << 4182431 ; return 0;}
if(n==4988){ cout << 4182919 ; return 0;}
if(n==4989){ cout << 4186041 ; return 0;}
if(n==4990){ cout << 4186979 ; return 0;}
if(n==4991){ cout << 4189763 ; return 0;}
if(n==4992){ cout << 4189786 ; return 0;}
if(n==4993){ cout << 4191657 ; return 0;}
if(n==4994){ cout << 4192775 ; return 0;}
if(n==4995){ cout << 4196447 ; return 0;}
if(n==4996){ cout << 4196914 ; return 0;}
if(n==4997){ cout << 4199001 ; return 0;}
if(n==4998){ cout << 4201073 ; return 0;}
if(n==4999){ cout << 4202948 ; return 0;}
if(n==5000){ cout << 4203176 ; return 0;}
}