Enigmatic Partition

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

题目描述

A partition of the number n is the set of numbers that all sum up to n. A partition $n = a_1 + a_2 + ... + a_m$ called enigmatic partition if it satisfies the following signatures:

$a_i$ is integer, $1 \le a_i \le n$ for $1 \leq i \leq m$ , and
$a_i \leq a_{i+1} \leq a_i + 1$ for $1 \leq i < m$ , and
$a_m = a_1 + 2$

Let f(n) be the number of n's enigmatic partitions. Given l and r, please calculate $\sum_{i=l}^r f(i)$ .

输入描述:

The first line contains the number of test cases T (). 
In each of the following T lines there are two integers l and r ().

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number and y is the answer.

示例1

输入

复制

输出

复制

Case #1: 2
Case #2: 7
Case #3: 8

说明

f(1) = 0.
f(2) = 0.
f(3) = 0.
f(4) = 0.
f(5) = 0.
f(6) = 1: 6 = 1 + 2 + 3.
f(7) = 1: 7 = 1 + 1 + 2 + 3.
f(8) = 2: 8 = 1 + 1+ 1 + 2 + 3, 8 = 1 + 2 + 2 + 3.
f(9) = 4: 9 = 1 + 1 + 1 + 1 + 2 + 3, 9 = 1 + 1 + 2 + 2 + 3, 9 = 1 + 2 + 3 + 3, 9 = 2 + 3 + 4