给定一个整数 $N$，请你统计 $1 \sim N$ 中有多少个数字包含 $49$。

包含 $49$ 是指一个数的连续两位为 $4$ 和 $9$，例如 $49,149,495,1499$ 等。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含一个整数 $N$。

输出格式

每组数据输出一行，一个整数，表示结果。

数据范围

$1 \le T \le 10000$,
$1 \le N \le 2^{63}-1$。

输入样例：

3
1
50
500

输出样例：

0
1
15