Les vaches de Farmer John s’intéressent à l’exploration des alentours de la ferme. Au départ, les $N$ $(1 \le N \le 1,000,000,000)$ vaches partent sur une route en un seul grand groupe. Lorsqu’il rencontre une bifurcation, le groupe choisit parfois de se diviser en deux groupes plus petits et non vides, chacun continuant sur l’une des routes. Lorsqu’un de ces groupes arrive à une autre bifurcation, il peut se diviser à nouveau, et ainsi de suite.

Les vaches ont conçu une manière particulière de se diviser : si elles peuvent former deux groupes dont les tailles diffèrent d’exactement $K$ $(1 \le K \le 1000)$, elles le font ; sinon, elles cessent d’explorer et commencent à brouter paisiblement.

En supposant qu’il y aura toujours de nouvelles bifurcations, calculez le nombre final de groupes de vaches broutant paisiblement.

Entrée

• Ligne $1$ : deux entiers $N$ et $K$, séparés par un espace.

Sortie

• Ligne $1$ : un entier représentant le nombre de groupes de vaches qui broutent.

Exemples

Entrée 1

6 2

Sortie 1

3

Remarque

Il y a 6 vaches et la différence de taille des groupes est 2.

Il y a 3 groupes finaux (contenant respectivement 2, 1 et 3 vaches).

   6
  / \
 2   4
    / \
   1   3

Auteur du problème : Aram Shatakhtsyan, 2007