题目如下：

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer $T(1<=T<=10000)$, indicating the number of test cases. For each test case, there will be an integer N(1<=N<=263−1)N (1 <= N <= 2^{63}-1)N(1<=N<=263−1) as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample

Input

3
1
50
500

Output

0
1
15

Hint

From 1 to 500, the numbers that include the sub-sequence “49” are “49”,“149”,“249”,“349”,“449”,“490”,“491”,“492”,“493”,“494”,“495”,“496”,“497”,“498”,“499”,
so the answer is 15.

题意简述：

求 $1$ 到 $n$ 含有 $49$ 的数字个数

题解 or 思路：

数位DP
我的方法是直接统计符合题意的个数，具体请参考下面的代码。
还有一种方法是 $n-不符合题意的个数$

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \\ios::sync_with_stdio(false); \\cin.tie(0);
#define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int n, a[30], f[30][2], p[30], idx;
int dfs(int pos, bool sta, bool lim)
{if (!pos)	return 0;if (!lim && f[pos][sta] != -1)	return f[pos][sta];int len = lim ? a[pos] : 9;int ans = 0;for (int i = 0; i <= len; i++){if (sta && i == 9)ans += lim ? n % p[pos - 1] + 1 : p[pos - 1];elseans += dfs(pos - 1, i == 4, lim && i == len);}if (!lim)	f[pos][sta] = ans;return ans;
}
void solve()
{cin >> n;int x = n;idx = 0;while (x)a[++idx] = x % 10, x /= 10;cout << dfs(idx, 0, 1) << '\\n';
}
signed main()
{buff;memset(f, -1, sizeof f);p[0] = 1;for (int i = 1; i < 30; i++)	p[i] = p[i - 1] * 10;int _ = 1;cin >> _;while (_--)solve();
}