Đi dạo

View as PDF

Time limit: 1.0s , Memory limit: 256M , Points: 10 (partial)

REF: Câu E HUE-ICT NAIVE & JUNIOR CHALLENGE - 2022

Nhà Bánh ở vùng ngoại ô với hàng rào gỗ màu xanh, đỏ rất đẹp. Ba lát thêm gạch cạnh hàng rào thành một con đường đi dạo xung quanh. Tương ứng với một cọc rào là một viên gạch và được đánh số từ 1 đến N như trên cọc gỗ hàng rào. Hàng ngày Bánh cùng em , Bi đi dạo quanh vườn để thưởng thức hương hoa lan vốn được trồng rất nhiều trong vườn. Tuy nhiên, do bước chân của các anh em đều ngắn không thể bước quá 3 viên gạch cho mỗi lần bước. Bánh hỏi nếu đi từ viên gạch thứ s đến viên gạch thứ e thì có bao nhiêu cách đi.

Anh chị hãy lập trình giúp Bánh.

Input

Dòng đầu tiên chứa số nguyên dương T là số testcase thỏa 1 \le T \le 10.

Dòng thứ hai chứa hai số nguyên s, e thỏa 1 \le s \le e \le 60.

Output

Ứng với mỗi testcase in kết quả trên một dòng.

Samples

Sample Input 1
5
2 5
3 8
1 1
10 30
1 30
Sample Output 1
4
13
1
121415
29249425

Comments


  • 1
    kimhuyenvt  commented on March 5, 2024, 6:33 a.m.

    ý tưởng giải bài này là gì vậy mọi người ơi????


      • 0
        hungdsss  commented on March 9, 2024, 4:29 a.m.

        quy hoạc động, số cách đến ô gạch thứ n sẽ bằng tổng số cách đến ô gạch thứ n - 1, n - 2, n - 3 <(")