Polycarpus loves lucky numbers. Everybody knows that lucky numbers are positive integers, whose decimal representation (without leading zeroes) contain only the lucky digits x and y. For example, if x = 4, and y = 7, then numbers 47, 744, 4 are lucky.

Let's call a positive integer a undoubtedly lucky, if there are such digits x and y (0 ≤ x, y ≤ 9), that the decimal representation of number a (without leading zeroes) contains only digits x and y.

Polycarpus has integer n. He wants to know how many positive integers that do not exceed n, are undoubtedly lucky. Help him, count this number.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^9) — Polycarpus's number.


-----Output-----

Print a single integer that says, how many positive integers that do not exceed n are undoubtedly lucky.


-----Examples-----
Input
10

Output
10

Input
123

Output
113



-----Note-----

In the first test sample all numbers that do not exceed 10 are undoubtedly lucky.

In the second sample numbers 102, 103, 104, 105, 106, 107, 108, 109, 120, 123 are not undoubtedly lucky.

Difficulty: interview

Starter code:

Solutions:
#CF Round 150. Div II Prob. A - Dividing Orange
import sys

dp = [[[-1 for j in range(3)] for i in range (1 << 10)] for k in range(11)]

In = sys.stdin
n = In.readline().strip()

def go (idx, mask, equal):
    if dp[idx][mask][equal] != -1:
        return dp[idx][mask][equal]
    if bin(mask).count("1") > 2:
        return 0
    if idx == len(n):
        return 1
    res = 0
    if idx == 0 or equal == 2:
        res += go(idx + 1, mask, 2)
    elif equal == 1 and int(n[idx]) == 0:
        res += go(idx + 1, mask | 1, 1)
    else:
        res += go(idx + 1, mask | 1, 0)    
    for i in range(1, 10):
        if equal == 1 and i > int(n[idx]):
            break
        elif equal == 1 and i == int(n[idx]):
            res += go(idx + 1, mask | (1 << i), 1)
        else:
            res += go(idx + 1, mask | (1 << i), 0)
    dp[idx][mask][equal] = res
    return res
    
print(go(0, 0, 1)  - 1)

def cnt(s, p):
    ans = 0
    if p > s: ans = 0
    elif len(p) == len(s):
        ans = 1 if len(set(p.lstrip('0'))) <= 2 else 0
    elif len(set(p.lstrip('0'))) > 2: ans = 0
    elif s[:len(p)] > p:
        if len(set(p.lstrip('0'))) == 2:
            ans = 2**(len(s)-len(p))
        elif len(set(p.lstrip('0'))) == 1:
            ans = 1 + 9 * (2**(len(s)-len(p)) - 1)
        else:
            # ab for all a, b != 0
            ans = 10 + 45 * (2**(len(s)-len(p)) - 2)
            ans += 36 * sum([2**l-2 for l in range(2,len(s)-len(p))])
                
    else: ans = sum(cnt(s, p+c) for c in '0123456789')

    return ans

print(cnt(input().strip(), '')-1)


n = str(int(input()) + 1)
a = int(n[0])
l = len(n)
d = 1 << (l - 1)

def f(a, i):
    nonlocal n, l
    if i == l: return 0
    b = int(n[i])
    i += 1
    d = 1 << (l - i)
    if a > b: return b * d + g(b, a, i)
    if a == b: return b * d + f(a, i)
    return (b - 1) * d + g(a, b, i) + 9 * d - 8
        
def g(a, b, i):
    nonlocal n, l
    if i == l: return 0
    c = int(n[i])
    i += 1
    d = 1 << (l - i)
    if c < a: return 0
    if c == a: return g(a, b, i)
    if c < b: return d
    if c == b: return d + g(a, b, i)
    return 2 * d

print(a * (9 * d - 8) + 72 * (d - l) + f(a, 1) - 1)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**9

n = int(input())
if n < 100:
    print(n)
    return
a = [[_,set(map(int,list(str(_))))] for _ in range(100)]
c = 99
for k in range(2,11):
    t = (10 ** (k-1))
    for aa in a:
        if aa[0] < t:
            aa[1] = aa[1] | set([0])
    at = a[:]
    for i in range(1,10):
        t = i * (10 ** k)
        for ai, ae in at:
            ac = ai + t
            if ac > n:
                print(c)
                return
            if len(ae) < 2:
                ae = ae | set([i])
            if i in ae and len(ae) < 3:
                c += 1
                a.append([ac,ae])


from copy import deepcopy

N = input()
A = [ ord( N[ i ] ) - ord( '0' ) for i in range( len( N ) ) ]

dp = [ 0, 0 ]
dp = [ deepcopy( dp ) for i in range( 10 + 1 ) ]
dp = [ deepcopy( dp ) for i in range( 10 + 1 ) ]
dp = [ deepcopy( dp ) for i in range( len( A ) + 1  ) ]
dp[ 0 ][ 10 ][ 10 ][ 0 ] = 1

for i in range( len( A ) ):
  for j in range( 10 + 1 ):
    for k in range( 10 + 1 ):
      for l in range( 2 ):
        lim = 9
        if not l:
          lim = A[ i ]
        for d in range( lim + 1 ):
          if d == 0 and j == 10 and k == 10:
            dp[ i + 1 ][ 10 ][ 10 ][ 1 ] += dp[ i ][ j ][ k ][ l ]
          else:
            if j == 10 or j == d:
              dp[ i + 1 ][ d ][ k ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ]
            else:
              if k == 10:
                if d < j:
                  dp[ i + 1 ][ d ][ j ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ]
                else:
                  dp[ i + 1 ][ j ][ d ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ]
              else:
                if d != j and d != k: continue
                dp[ i + 1 ][ j ][ k ][ l or d < lim ] += dp[ i ][ j ][ k ][ l ]

ans = 0
for i in range( 10 ):
  for j in range( 10 + 1 ):
    for k in range( 2 ):
      ans += dp[ len( A ) ][ i ][ j ][ k ]

print( ans )


def cnt(s, p):

    ans = 0

    if p > s: ans = 0

    elif len(p) == len(s):

        ans = 1 if len(set(p.lstrip('0'))) <= 2 else 0

    elif len(set(p.lstrip('0'))) > 2: ans = 0

    elif s[:len(p)] > p:

        if len(set(p.lstrip('0'))) == 2:

            ans = 2**(len(s)-len(p))

        elif len(set(p.lstrip('0'))) == 1:

            ans = 1 + 9 * (2**(len(s)-len(p)) - 1)

        else:

            # ab for all a, b != 0

            ans = 10 + 45 * (2**(len(s)-len(p)) - 2)

            ans += 36 * sum([2**l-2 for l in range(2,len(s)-len(p))])

                

    else: ans = sum(cnt(s, p+c) for c in '0123456789')



    return ans



print(cnt(input().strip(), '')-1)





# Made By Mostafa_Khaled


n=int(input())
curr=list([i for i in range(1,100)]) 
curr=set(curr)
def isvalid(x):
    if x<1 or x>10**9:
        return 0 
    if len(set(str(x)))<=2:
        return 1 
cnt=0 
while cnt<=10**5 :
    curr1=set()
    for i in curr:
        for j in range(10):
            if isvalid(i*10+j):
                curr1.add(i*10+j)
               # print('hi')
                cnt+=1 
    #print(curr1)
    curr|=curr1 
curr=sorted(list(curr))
#print(curr)
ans=0 
for i in curr:
    if i>=1 and i<=n:
        ans+=1 
    elif i>n:
        break 
print(ans)

n=int(input())
curr=list([i for i in range(1,100)]) 
curr=set(curr)
def isvalid(x):
    if x<1 or x>10**9:
        return 0 
    if len(set(str(x)))<=2:
        return 1 
cnt=0 
while cnt<=9*(10**4 ):
    curr1=set()
    for i in curr:
        for j in range(10):
            if isvalid(i*10+j):
                curr1.add(i*10+j)
               # print('hi')
                cnt+=1 
    #print(curr1)
    curr|=curr1 
curr=sorted(list(curr))
#print(curr)
ans=0 
for i in curr:
    if i>=1 and i<=n:
        ans+=1 
    elif i>n:
        break 
print(ans)

n=int(input())
curr=list([i for i in range(1,100)]) 
curr=set(curr)
def isvalid(x):
    if x<1 or x>10**9:
        return 0 
    if len(set(str(x)))<=2:
        return 1 
cnt=0 
while cnt<=10**5:
    curr1=set()
    for i in curr:
        for j in range(10):
            if isvalid(i*10+j):
                curr1.add(i*10+j)
            
                cnt+=1 
    #print(curr1)
    curr|=curr1 
curr=sorted(list(curr))
#print(curr)
ans=0 
for i in curr:
    if i>=1 and i<=n:
        ans+=1 
    elif i>n:
        break 
print(ans)

n = int(input())
res = set()

def solve(p, l):
    if p > n or l > 10:
        return
    if p > 0:
        res.add(p)
    solve(p * 10 + a, l + 1)
    solve(p * 10 + b, l + 1)

for a in range(0, 10):
    for b in range(0, a):
        solve(0, 0)
print(len(res))


# https://codeforces.com/contest/244/problem/B

def gen(digit, x, length, S):
    S.append(x)
    
    if length == 10:
        return
    
    if len(digit) == 1:
        for i in range(0, 10):
            next_x = x * 10 + i
            
            if i == digit[0]: 
                gen(digit, next_x, length+1, S)
            else:
                gen(digit+[i], next_x, length+1, S)
        
    else:
        next_x1 = x * 10 + digit[0]
        next_x2 = x * 10 + digit[1]
        gen(digit, next_x1, length+1, S)
        gen(digit, next_x2, length+1, S)
        
S = []
for i in range(1, 10):
    gen([i], i, 1, S)
    
S = sorted(S) 
x = int(input())

l = -1
u = len(S)

while u-l>1:
    md = (u+l) // 2
    if x >= S[md]:
        l = md
    else:
        u = md
print(u)            

n=int(input())
a=[]
def foo(x,i,j):
    if x>n:
        return
    if x:
        a.append(x)
    if 10*x+i!=x:
        foo(10*x+i,i,j)
    foo(10*x+j,i,j)
for i in range(10):
    for j in range(i+1,10):
        foo(0,i,j)
print(len(set(a)))


ii=lambda:int(input())
kk=lambda:map(int, input().split())
ll=lambda:list(kk())
q =[]
s=set()
n=ii()
for x in range(10):
	for y in range(10):
		q.append(x)
		while q:
			q2 = []
			for item in q:
				if item > 0 and item <= n:
					s.add(item)
					item*=10
					q2.append(item+x)
					q2.append(item+y)
			q=q2
print(len(s))

num=int(input());cou=0;
def traverse(x):
    if(x>num):return
    nonlocal cou
    if(len(set([int(j) for j in str(x)]))<=2):
        cou+=1
        for i in range(0,10):traverse(10*x+i)
for i in range(1,10):traverse(i)
print(cou)

from collections import deque
def check(n):
    s=set([int(i) for i in str(n)])
    if len(s)<=2:
        return 1
    else:
        return 0
n=int(input())
s=set()
q=deque()
q.append(0)
while(len(q)>0):
    g=q.popleft()
    if g>n:
        break
    s.add(g)
    if g>=n:
        break
    for j in range(0,10):
        if g*10+j not in s and check(g*10+j):
            q.append(g*10+j)

print(len(s)-1)

n=int(input())
array=set()
array.add(10**9)
for x in range(10):
    for y in range(10):
        for l in range(1, 10):
            for m in range(1, 2 ** l + 1):
                s = [str(x) if m & (1 << i) else str(y) for i in range(l)]
                u = int(''.join(s))
                if u <= n:
                    array.add(u)
array.remove(0)
# print (sorted(list(array)))
array=[u for u in array if u <= n]
print(len(array))

def p(k):
    if 0 < k <= n:
        s.add(k)
        k *= 10
        p(k + x)
        p(k + y)


n = int(input())
s = set()
for x in range(10):
    for y in range(10):
        p(x)
print(len(s))


"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by adi0311(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest, _heapify_max, _heapreplace_max
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from fractions import Fraction
# sys.setrecursionlimit(2*pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outln(var): sys.stdout.write(str(var)+"\n")
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return list(map(int, data().split()))
def ssp(): return list(map(str, data().split()))
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


temp = pow(10, 8)


def dfs(number):
    if 0 < number <= n:
        answer[0] += 1
    if number >= temp:
        return
    for i in range(10):
        if number * 10 + i > 0:
            if len(set(str(number * 10 + i))) <= 2:
                dfs(number * 10 + i)


n = int(data())
answer = [0]
dfs(0)
if n == pow(10, 9):
    outln(answer[0] + 1)
    return
outln(answer[0])


def dfs(num):
  if 0 < num <= n:
    s.add(num)
    num*=10
    dfs(num+x)
    dfs(num+y)


n = int(input())
s = set()
for x in range(10):
  for y in range(10):
    dfs(x)
    
print(len(s))


def dfs(num):
  if 0 < num <= n:
    s.add(num)
    num*=10
    dfs(num+x)
    dfs(num+y)


n = int(input())
s = set()
for x in range(10):
  for y in range(10):
    dfs(x)
    
print(len(s))

def find(x):
    if 0<x<=n:
        p.add(x)
        x*=10
        find(x+i)
        find(x+j)
n=int(input())
p= set()
for i in range(10):
    for j in range(10):
        find(i)
print(len(p))



def dfs(num):
  if 0 < num <= n:
    s.add(num)
    num*=10
    dfs(num+x)
    dfs(num+y)

n = int(input())
s = set()
for x in range(10):
  for y in range(10):
    dfs(x)

print(len(s))

#Copied


#d=sorted(d,key=lambda x:(len(d[x]),-x))  d=dictionary     d={x:set() for x in arr}
#n=int(input())
#n,m,k= map(int, input().split())
import heapq
#for _ in range(int(input())):
#n,k=map(int, input().split())
#input=sys.stdin.buffer.readline
#for _ in range(int(input())):
def dfs(x):
    if 0< x <=n :
        s.add(x)
        x*=10
        dfs(x+i)
        dfs(x+j)

n=int(input())
#arr = list(map(int, input().split()))
s=set()

for i in range(1,10):
    for j in range(10):
        dfs(i)
print(len(s))