Equipment Amplification¶
- Indicative time limit: 1.0 seconds.
- Judge time limit: twice the reference program’s largest per-case median on the target platform, rounded up to a multiple of 0.5 seconds.
- Memory limit: 128 MB.
- Reference environment and measurements
Story¶
Equipment amplification may succeed or downgrade an item. A smith is investigating a success rule based on digits and wants to count the successful values in several ranges.
Formal Problem Statement¶
Write a nonnegative integer \(S\) in binary and decimal. In both representations, number positions from the least significant digit as \(0,1,\ldots\) and pad with infinitely many leading zeros. Let the digits be \(b_i\) and \(d_i\) .
Call \(S\) successful if \(b_i\ge d_i\) at every position. For example, decimal \(10\) is binary \(1010\) and is successful. Decimal \(1010\) is binary \(1111110010\) ; its binary digit at position \(3\) is smaller than its decimal digit, so it is unsuccessful.
For each of \(q\) queries, given a nonnegative integer \(N\) , count the successful integers satisfying \(0\le S\le N\) . Apply the same rule to \(0\) .
Input¶
The first line contains \(q\) . Each of the following \(q\) lines contains a decimal integer \(N\) .
Output¶
Print \(q\) lines, one count for each query.
Sample 1¶
Input¶
2
55
6
Output¶
4
2
Sample 2¶
Input¶
4
0
1
10
1010
Output¶
1
2
3
10
Sample 3¶
Input¶
3
999999999999999999999999999999
111111111111111111111111111111
0
Output¶
715704
715704
1
Sample Explanation¶
In sample 1, the successful values at most \(55\) are \(0,1,10,11\) . Those at most \(6\) are \(0,1\) .
Constraints and Guarantees¶
\(1\le q\le100\) ; \(0\le N\le10^{30}-1\) . The source-code size limit is 50 KB.
| Score | Additional conditions |
|---|---|
| 100% | None |