### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

It is well-known that the sum of any range **Sum[l; r]** can be rewritten in form **Sum[0; r]-Sum[0; l-1]**. Let **Sum4[i]** is the total number of digits **4** in all numbers from **1** to **i**, inclusive, and **Sum7[i]** is the total number of digits **7** in all numbers from **1** to **i**, inclusive. We need to find the number of such pairs **(l; r)** that **1 <= l <= r <= N** and **Sum4[r]-Sum4[l-1] = Sum7[r]-Sum7[l-1]**. Rewrite it in this way: **Sum4[l-1]-Sum7[l-1] = Sum4[r]-Sum7[r]**. We can iterate through all r from **1** to **N**, and for each **r** we need to know the number of correct **l** indexes. Let **S = Sum4[r]-Sum7[r]** for some current r. We need to find the number of such **l (l <= r) that Sum4[l-1]-Sum7[l-1] = S**. Since we are iterating **r** through all numbers from **1** to **N**, we can handle some array **C[i]**, where **C[i]** is current number of such **l** that **Sum4[l]-Sum7[l] = i**. In each iteration of **r**, we add to the result number **C[Sum4 [r]-Sum7[r]]**, and then increment **C[Sum4[r]-Sum7[r]]** by **1**. In general this array can has negative indexes so if your programming language does not support arbitrary indexation you should make some tricks. But it can be proven that **Sum4[r]-Sum7[r]** is always non-negative so you can use usual array for this. Also it is useful to handle arrays **Cnt4[i]** and **Cnt7[i]** where **Cnt4[i]** is the number of fours of decimal representation of i and similar definition is for **Cnt7[i]**. Then **Cnt4[i]** can be calculated in **O(1)** time from **Cnt4[i/10]**. Thus the total complexity of such algorithm is **O(N)** for one query. But, you can precompute results for all numbers from **1** to **10**^{5} and store them in some array. That gives **O(1)** complexity for each query.

And here is some example: test case for **N = 10**.

i | Sum4[i] | Sum7[i] | Sum4[i]-Sum7[i] | C[-1] | C[0] | C[1] | Result |

0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |

1 | 0 | 0 | 0 | 0 | 2 | 0 | 1 |

2 | 0 | 0 | 0 | 0 | 3 | 0 | 3 |

3 | 0 | 0 | 0 | 0 | 4 | 0 | 6 |

4 | 1 | 0 | 1 | 0 | 4 | 1 | 6 |

5 | 1 | 0 | 1 | 0 | 4 | 2 | 7 |

6 | 1 | 0 | 1 | 0 | 4 | 3 | 9 |

7 | 1 | 1 | 0 | 0 | 5 | 3 | 13 |

8 | 1 | 1 | 0 | 0 | 6 | 3 | 18 |

9 | 1 | 1 | 0 | 0 | 7 | 3 | 24 |

10 | 1 | 1 | 0 | 0 | 8 | 3 | 31 |

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.