Một số nguyên dương n được tính là pro vjp nếu tách các chữ số trong số đấy ra thì tụi nó đều y hệt nhau. Điển hình như là: 1, 2 và 99 sẽ được gọi là pro vjp, nhưng 719 và 2021 thì không.

Cho 1 số n, tìm số lượng các số pro vjp nằm trong khoảng từ 1 tới n.

Input
Dòng đầu tiên chứa 1 số t (1≤t≤~10^4~). Sau đất sẽ có t test cases theo sau.

Mỗi test case sẽ có duy nhất một số nguyên n (1≤n≤~10^9~).

Output
Ứng với mỗi test case, in ra số lượng các chữ số pro vjp có trong khoảng từ 1 tới n.

Examples
Input

6
1
2
3
4
5
100

Output

1
2
3
4
5
18