Description

反恐怖分子在尘土中发现了一枚定时炸弹，但这次恐怖分子改进了定时炸弹。定时炸弹的数字序列从$1$到$n$。若当前的数字序列包括子序列“$49$”，则爆炸的力量会增加一个点。现在反恐人员知道了数字$n$，他们想知道最后的力量点。

Format

Input

输入的第1行包含一个整数$T（1≤T≤10000）$，表示测试用例的数量。对每个测试用例，都有一个整数$n（1≤n≤2^{63}-1）$作为描述。

Output

对每个测试用例，都输出一个整数，表示最终的力量点。

提示：$[1,500]$区间包括$“49”$的数是$49、149、249、349、$$449、490、491、492、$$493、494、495、496、$$497、498、499，$所以答案是$15$。

Samples

3
1
50
500

0
1
15

来源

HDU3555