题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 $1$ 到 $40$ 中这样的数包括 $1、2、9、10$ 至 $32、39$ 和 $40$，共 $28$ 个。

请问，在 $1$ 到 $X$ 中，所有这样的数有多少个？ 为避免答案过大，请输出答案除以 $10^9+7$ 的余数。

输入描述

第一行包一个整数 $N$，表示测试数据的规模。

接下来 $N$ 行每行 $1$ 个整数 $X$。

输出描述

对每个输入输出一个整数表示答案。

4
40
100
2019
123456789

28
58
1761
121441251

评测用例规模与约定：

对于所有评测用例，$1≤N≤100,1≤X≤10^{100}$。