Divizorus

Cerință

Se dau $q$ întrebări de tipul:

Pentru $l$, $r$ și $k$ date, există două numere naturale nu neapărat distincte $a$ și $b$ care să respecte următoarele condiții?

1. $l \le a,b \le r$
2. Cel mai mare divizor comun al numerelor $a$ și $b$ este egal cu $k$.

Date de intrare

Prima linie a fișierului de intrare divizorus.in va conține numărul de întrebări $q$.

Pe fiecare dintre următoarele $q$ linii se vor afla câte trei numere $l$, $r$ și $k$.

Date de ieșire

Fișierul de ieșire divizorus.out va conține $q$ cifre (0=NU, 1=DA), răspunsurile la cele $q$ întrebări.

Restricții și precizări

• $1 \le q \le 2 \cdot 10^5$
• $1 \le l,r,k \le 10^9$, $l \le r$.

  #	Punctaj	Restricții
  1	30	$1 \le q,l,r,k \le 100$
  2	20	$k \le 100$
  3	20	$k \ge 2 \cdot 10^8$
  4	30	Fără restricții suplimentare

Exemplul 1

divizorus.in

4
1 5 2
50 100 1
50 100 40
50 100 50

divizorus.out

1 1 0 1

Explicație

• Pentru prima întrebare, avem $a=2$ și $b=4$ cu cel mai mare divizor comun egal cu $2$.
• Pentru a doua întrebare, avem, de exemplu, $a=68$ și $b=69$ cu cel mai mare divizor comun egal cu $1$.
• Pentru a treia întrebare, nu există două numere din intervalul dat cu cel mai mare divizor egal cu $40$.
• Pentru a patra întrebare, avem $a=50$ și $b=100$ cu cel mai mare divizor comun egal cu $50$.