POLSKI SPOJ

Miałeś już okazję zapoznać się z liczbami sfenicznymi chociażby rozwiązując jedno z zadań próbnym VII edycji konkursu "FRAKTAL". Przypomnijmy: liczba sfeniczna, to taka liczba naturalna, która rozkłada się na iloczyn dokładnie trzech różnych liczb pierwszych. Utrudnijmy to zadanie i zdefiniujmy liczbę k-sfeniczną. Liczbę k-sfeniczną nazywamy taką, która rozłoży się na iloczyn dokładnie k różnych liczb pierwszych. Zadanie polega na napisaniu programu, który będzie odpowiadać na pytanie, ile podano liczb k-sfenicznych w ciągu liczb naturalnych dodatnich począwszy od indeksu w przedziale [a..b], gdzie a to indeks początkowy przedziału, natomiast b to indeks końcowy (wyrazy ciągu indeksujemy od 1).

Wejście

W pierwszym wierszu jedna liczba naturalna n określająca długość ciągu (nie więcej niż milion).

W drugim wierszu n liczb naturalnych dodatnich nie większych niż milion.

Następnie jedna liczba q określająca liczbę zapytań. Każde zapytanie składa się z trzech liczb całkowitych a, b i k takich, że 1 ≤ a ≤ b ≤ n definiujących przedział [a..b] oraz 1 ≤ k ≤ 20, określająca ilość liczb pierwszych w rozkładzie badanych liczb.

Wyjście

Dla każdego zapytania jedna liczba określająca liczbę liczb sfenicznych o k rozkładzie.

Przykład

Wejście:
7
3 6 8 9 20 13 80
5
1 7 3
1 7 1
2 6 2
5 7 3
1 1 1

Wyjście:
0
2
1
0
1