题目描述

远古的Pascal人也使用阿拉伯数字来进行计数，但是他们又不喜欢使用7，因为他们认为7是一个不吉祥的数字，所以Pascal数字8其实表示的是自然数中的7，18表示的是自然数中的16。下面计算一下，在正整数n范围以内包含有多少个Pascal数字。

输入格式

第一行为正整数t，接下来t行，每行一个正整数n(≤2^32-1)。

输入的是Pascal数字

$t \leq 10000$

输出格式

对于每个正整数n，输出n以内的Pascal数的个数。

2
10
20

9
18