#LUDIC1. Ludic Numbers (medium)
Ludic Numbers (medium)
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css" integrity="sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0" crossorigin="anonymous">
Find the number of Ludic numbers less than or equal to $N$.
Input
The first line contains $T$ ($1 \le T \le 1000$), the number of test cases.
Each test case contains a single integer $N$ ($1 \le N \le 10^9$).
Output
For each test case, output the number of Ludic numbers less than or equal to $N$.
Example
Input
10 1 2 3 4 5 10 100 1000 1000000 1000000000
Output
1 2 3 3 4 5 24 142 66164 43956562
Note
- See LUDIC2 for a harder version.
- Other references for the Ludic numbers: Ludic numbers or A003309.