244_B. Undoubtedly Lucky Numbers_28616
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 ≤ 109) — 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.
#include <bits/stdc++.h>
using namespace std;
int ans = 0, n;
int numDistDig(int n) {
  vector<int> arr(10, 0);
  while (n > 0) {
    arr[n % 10]++;
    n /= 10;
  }
  int ans = 0, i;
  for (i = 0; i < 10; i++) ans += (arr[i] > 0);
  return ans;
}
void dfs(int num) {
  if (num > 0 && num <= n) ans++;
  if (ans >= 100000000) return;
  int i;
  for (i = 0; i < 10; i++) {
    int num2 = num * 10 + i;
    if (num2 > 0 && numDistDig(num2) <= 2) dfs(num2);
  }
}
int main() {
  scanf("%d", &n);
  dfs(0);
  printf("%d\n", ans);
}

123
 10
 784262
 68
 101
 132
 999999998
 468390
 603356456
 820040584
 2
 909090901
 642678
 999999999
 940
 326806
 4
 6
 1000
 356
 999999997
 102
 8
 64214872
 89
 3
 72
 1
 5
 7
 442198
 1000000000
 9
 142498040
 1106646
 0
 111
 178
 631770
 380204978
 12
 999905083
 538039
 223
 596596
 15
 1100
 128
 415673571
 203
 94963945
 133
 69
 844018
 14
 234298201
 20
 16
 854133
 100
 183
 2382
 626243410
 21
 242459604
 640288
 446
 998397
 11
 114
 330499271
 387
 1726751
 25
 13
 83914
 17
 467680878
 29
 798225
 266
 4401
 35
 280567712
 44530
 688
 1593671
 18
 156
 411029171
 574
 1984115
 30
 24
 127752
 33
 811844381
 36
 249621
 364
 8261
 50
 16665
 744
 2404751
 56
 304531400
 498
 378069871

113
 10
 4079
 68
 101
 114
 40742
 3223
 31623
 36407
 2
 38532
 3615
 40743
 331
 2759
 4
 6
 352
 175
 40741
 101
 8
 15759
 89
 3
 72
 1
 5
 7
 3071
 40744
 9
 21671
 4719
 0
 103
 123
 3599
 26711
 12
 40471
 3335
 135
 3543
 15
 356
 113
 27223
 129
 19239
 115
 69
 4175
 14
 23903
 20
 16
 4191
 100
 124
 455
 31895
 21
 23967
 3615
 198
 4599
 11
 106
 25119
 180
 5159
 25
 13
 1911
 17
 28879
 29
 4103
 149
 560
 35
 24415
 1411
 265
 5111
 18
 119
 27095
 233
 5223
 30
 24
 2319
 33
 36327
 36
 2631
 176
 809
 50
 1038
 276
 5615
 56
 24799
 210
 26711
