Description

The ancient Pascal people also used Arabic numerals to count, but they disliked using $7$ because they considered $7$ an unlucky number. Therefore, Pascal number $8$ actually represents $7$ in the natural numbers, and $18$ represents $16$. Please compute how many Pascal numbers are contained within the range of positive integers up to $n$.

Input Format

The first line contains a positive integer $t$. Then follow $t$ lines, each containing a positive integer $n$, and it is guaranteed that the input $n$ is a Pascal number.

Output Format

For each positive integer $n$, output the number of Pascal numbers not exceeding $n$.

2
10
20

9
18

Hint

For all testdata, $1 \leq t \leq 10000$, $1 \leq n \leq 2^{32} - 1$.

Translated by ChatGPT 5