Algorithm


B. Ordinary Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call a positive integer n ordinary if in the decimal notation all its digits are the same. For example, 1122 and 9999 are ordinary numbers, but 719719 and 20212021 are not ordinary numbers.

For a given number n, find the number of ordinary numbers among the numbers from 11 to n.

Input

The first line contains one integer t (1t1041≤�≤104). Then t test cases follow.

Each test case is characterized by one integer n (1n1091≤�≤109).

Output

For each test case output the number of ordinary numbers among numbers from 11 to n.

Example
input
Copy
6
1
2
3
4
5
100
output
Copy
1
2
3
4
5
18

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  const int MAX = 10;
  int t;
  cin>>t;
  int n;
  while(t--){
    cin>>n;
    int arr[MAX];
    int r = log10(n);
    int tmp = 0;
    for (int i = 0; i < r+1; i++) {
      tmp = tmp * 10 + 1;
    }
    cout<<(r * 9 + n / tmp)<<endl;
  }
  return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6
1
2
3
4
5
100

Output

x
+
cmd
1
2
3
4
5
18
Advertisements

Demonstration


Codeforcess Solution  1520-B B. Ordinary Numbers ,C++, Java, Js and Python,1520-B B.Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+