Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let F_{d}(x) equals to the number of digits d in decimal representation of the positive integer x. Chef interests only in functions F_{4}(x) and F_{7}(x). For the given positive integer N he wants to know the total number of different pairs (L; R) such that  F_{4}(L) + F_{4}(L + 1) + ... + F_{4}(R) equals to  F_{7}(L) + F_{7}(L + 1) + ... + F_{7}(R) and 1 ≤  L ≤ R ≤ N.

------ Input ------ 

The first line contains a single positive integer T, the number of test cases. T test cases follow. The only line of each test case contains a positive integer N .

------ Output ------ 

For each test case, output a single line containing the answer for the corresponding test case.

------ Constraints ------ 

1 ≤ T ≤ 100000

1 ≤ N ≤ 100000

----- Sample Input 1 ------ 
3
3
10
100
----- Sample Output 1 ------ 
6
31
1266

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc


Solutions:
def precompute():
	n = 100000
	d = {0: 1}
	s4 = [0]
	s7 = [0]
	for i in range(1, n + 1):
		v = str(i)
		s4.append(s4[-1] + v.count('4'))
		s7.append(s7[-1] + v.count('7'))
	s4_7 = [0]
	for i in range(1, n + 1):
		s4_7.append(s4[i] - s7[i])
	ans = [0]
	for i in range(1, n + 1):
		v = s4_7[i]
		if v in d:
			ans.append(ans[-1] + d[v])
			d[v] += 1
		else:
			ans.append(ans[-1])
			d[v] = 1
	return ans
ans = precompute()
for _ in range(int(input())):
	print(ans[int(input())])


m = [0] * (10 ** 5 + 1)
c = [0] * 12000
k = 0
m[1] = 1
c[0] = 1
for i in range(2, 10 ** 5 + 1):
	j = i
	while j > 0:
		d = j % 10
		if d == 4:
			k += 1
		elif d == 7:
			k -= 1
		j //= 10
	m[i] = m[i - 1] + c[k]
	if k == 0:
		m[i] += 1
	c[k] += 1
for _ in range(int(input())):
	n = int(input())
	print(m[n])


from functools import lru_cache

@lru_cache(None)
def dp(n, k):
	if n < k:
		return 0
	if n == k:
		return 1
	base = 10 ** (len(str(n)) - 1)
	upper = (k + 1) * base - 1
	ans = n >= k * base and min(n - k * base + 1, base)
	return ans + dp(base - 1, k) * (n // base) + dp(n % base, k)
cnt = {0: 1}
memo = [0]
for i in range(1, 100001):
	diff = dp(i, 4) - dp(i, 7)
	memo.append(memo[-1] + cnt.get(diff, 0))
	cnt[diff] = cnt.get(diff, 0) + 1
for i in range(int(input())):
	print(memo[int(input())])