Se consideră șirul numerelor Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....

Șirul este definit astfel:

• fib[1] = 1, fib[2] = 1
• fib[i] = fib[i-1] + fib[i-2], unde fib[i] reprezintă al i-lea număr Fibonacci.

Spunem că un număr natural x este fibopower dacă acesta se poate descompune în produs de trei numere Fibonacci distincte. Exemplu: numărul 48 este un număr fibopower deoarece 48 = 2 • 3 • 8.

Se consideră șirul A = (A[1], A[2], ..., A[n] cu n elemente numere naturale nenule, respectiv un număr natural k cuprins între 1 și n. O secvență a șirului A este formată din valori situate pe poziții consecutive în A: A[i], A[i+1], ..., A[j], unde 1 ≤ i ≤ j ≤ n.

Pe șirul A se fac q interogări de tipul x y cu semnificația: să se determine numărul secvențelor A[i], A[i+1], ..., A[j] cu x ≤ i ≤ j ≤ y care conțin exact k numere fibopower.

Cerința

Fiind cunoscute n, k, q și cele n elemente ale șirului A, să se determine răspunsul pentru cele q interogări date.

Date de intrare

Fișierul de intrare fibopower.in conține pe prima linie numerele naturale n, k și q, cu semnificația din enunț. Pe a doua linie se află n numere naturale nenule ce reprezintă elementele șirului A. Pe următoarele q linii, sunt scrise cele q interogări, câte o interogare pe o linie, sub forma a două numere naturale x y, cu semnificația din enunț. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire fibopower.out va conține q linii, pe linia i (1 ≤ i ≤ q) fiind scris răspunsul la cea de a i-a interogare din fișierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ q ≤ 100.000
• 1 ≤ k ≤ n
• 1 ≤ A[i] ≤ 1.000.000.000, pentru 1 ≤ i ≤ n
• Pentru orice întrebare 1 ≤ x ≤ y ≤ n
• Pentru 26 de puncte, 1 ≤ n ≤ 1000, q = 1, x = 1, y = n
• Pentru 27 de puncte, 1000 < n ≤ 100.000, q = 1, x = 1, y = n
• Pentru 8 puncte, 1 < n ≤ 100, 1 < q ≤ 100
• Pentru 9 puncte, 100 < n, q ≤ 3500
• Pentru 8 puncte, n = 100.000, k = 1
• Pentru 22 de puncte, fără restricții suplimentare.

Exemplu:

fibopower.in

6 2 2
5 6 21 48 6 9
1 6
2 5

fibopower.out

6
3

Explicație

n=6, k=2. În șir există 3 numere fibopower: A[2], A[4], A[5]. Avem de rezolvat 2 interogări. La prima interogare trebuie să determinăm câte secvențe aflate între pozițiile 1, 6 în șir conțin exact 2 numere fibopower.
Sunt 6 astfel de secvențe:

• 5 6 21 48
• 6 21 48
• 21 48 6
• 21 48 6 9
• 48 6
• 48 6 9

La a doua interogare răspunsul este 3, cele 3 secvențe fiind:

• 6 21 48
• 21 48 6
• 48 6