Query Theory I

题号：NC206675
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

XiaoYang is building a big system, which uses the pattern of Command Query Responsibility Segregation.

This system holds an array of numbers $\lbrace a_i \rbrace$ of length n, where $a_i = i$ for all $i \in [1, n]$ . And it is designed for a function f(L, R).

$f(L, R) = \sum_{i=L}^R \sum_{j|i} j$

You are developing this system with XiaoYang. Now, Q queries are here for the sequence with $n = 10^6$ . Each query contains two number L, R. You should respond to these queries with the result of that function.

输入描述:

The input starts with one line, containing integers $Q ~ (1 \leq Q \leq 10^5)$ .

Then follow Q lines, each containing integers $L, R ~ (1 \leq L \leq R \leq 10^6)$ denoting the query parameters.

输出描述:

For each query, output the answer in one line.

示例1

输入

复制

1
1 5

输出

复制

说明

For the first query, f(1, 5) = 1 + 3 + 4 + 7 + 6 = 21.