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: MEDIUM_HARD
Tags: Bit manipulation

Graph traversal

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
nset = set()
n = int(input())

def reslove(x, y, num, flag):
	if num > n or (flag and num == 0):
		return
	if num > 0:
		nset.add(num)
	reslove(x, y, num * 10 + x, True)
	reslove(x, y, num * 10 + y, True)
for i in range(10):
	for j in range(i + 1, 10):
		reslove(i, j, 0, False)
print(len(nset))


def func(num):
	if 0 < num <= n:
		result.add(num)
		num *= 10
		func(num + x)
		func(num + y)
n = int(input())
result = set()
for x in range(10):
	for y in range(10):
		func(x)
print(len(result))


def findNum(num):
	if 0 < num <= n:
		s.add(num)
		num *= 10
		findNum(num + x)
		findNum(num + y)
n = int(input())
s = set()
for x in range(10):
	for y in range(10):
		findNum(x)
print(len(s))


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)
	sys.exit()
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)
				sys.exit()
			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]
					elif j == 10 or j == d:
						dp[i + 1][d][k][l or d < lim] += dp[i][j][k][l]
					elif 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 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 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:
			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 = int(input())
use = set()

def calc(x, a, b):
	global cnt
	if int(x) <= n and (not int(x) in use):
		use.add(int(x))
	elif int(x) > n:
		return
	calc(x + a, a, b)
	calc(x + b, a, b)

def calc2(x, a):
	global cnt
	if int(x) <= n and (not int(x) in use):
		use.add(int(x))
	elif int(x) > n:
		return
	calc2(x + a, a)
for i in range(1, 10):
	calc2(str(i), str(i))
for i in range(10):
	for j in range(i + 1, 10):
		if i != 0:
			calc(str(i), str(i), str(j))
		calc(str(j), str(i), str(j))
print(len(use))


import heapq

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


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
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 map(int, data().split())

def ssp():
	return 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)
	exit()
outln(answer[0])


n = int(input().strip())
if n < 102:
	print(n)
else:
	from itertools import product
	res = set()
	combination = (str(i) + str(j) for i in range(10) for j in range(i + 1, 10))
	for it in (product(comb, repeat=l) for comb in combination for l in range(1, len(str(n)) + 1)):
		for line in it:
			tmp = int(''.join(line))
			if tmp and tmp <= n:
				res.add(tmp)
	print(len(res))


s = set()

def find(x, y, num):
	s.add(num)
	xx = x + num * 10
	yy = y + num * 10
	if xx <= n and xx != 0:
		find(x, y, xx)
	if yy <= n and yy != 0:
		find(x, y, yy)
n = int(input())
for i in range(1, 10):
	for j in range(0, 10):
		find(i, j, 0)
print(len(s) - 1)


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)


n = int(input())

def bruteforce(number):
	res = 0
	liste = []
	while number > 0:
		integer = number % 10
		if integer not in liste:
			liste.append(integer)
		number = number // 10
	return len(liste) <= 2
answer = [0]

def dfs(num):
	if num > 0 and num <= n:
		answer[0] += 1
		for a in range(10):
			if bruteforce(num * 10 + a):
				dfs(num * 10 + a)
for chiffre in range(1, 10):
	dfs(chiffre)
print(answer[0])


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)


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

def f(a, i):
	global 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):
	global 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)


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)


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())
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))


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
	curr |= curr1
curr = sorted(list(curr))
ans = 0
for i in curr:
	if i >= 1 and i <= n:
		ans += 1
	elif i > n:
		break
print(ans)


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)))


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))


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)
array = [u for u in array if u <= n]
print(len(array))


s = set()

def DFS(x, y, num):
	s.add(num)
	num_x = 10 * num + x
	num_y = 10 * num + y
	if num_x and num_x <= n:
		DFS(x, y, num_x)
	if num_y and num_y <= n:
		DFS(x, y, num_y)
n = int(input())
for i in range(10):
	for j in range(i, 10):
		DFS(i, j, 0)
print(len(s) - 1)


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import stdin, stdout
from io import BytesIO, IOBase
from itertools import accumulate
from collections import deque

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a
res = set()

def solve(p, l, a, b):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solve(p * 10 + a, l + 1, a, b)
	solve(p * 10 + b, l + 1, a, b)
n = int(input())
for a in range(0, 10):
	for b in range(0, a):
		solve(0, 0, a, b)
print(len(res))


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))