Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

P0012. Diabolical numbers P79123

Statement

html

We say that a number is diabolical if it is divisible for the double of the sum of its digits in basis 4. Your task is to write a program that, given a sequence of integers strictly positive finished in −1 , counts how many of them are diabolical.

Your program must include and use the function

bool is_diabolical(int n);

that indicates if an integer |n| strictly positive is diabolical or is not.

These are some instances:

n	1	4	6	17	20	23	28	140	255	999999972
n in basis 4	1	10	12	101	110	113	130	2030	3333	323212230213210
sum of the digits	1	1	3	2	2	5	4	5	12	27
diabolical	No	Yes	Yes	No	Yes	No	No	Yes	No	Yes

Input

The input consists of a sequence of integers strictly positive finished in −1-

Output

Your program must print the quantity of diabolical numbers of the sequence, with six digits. (The inputs will always have less than a million diabolical numbers.)

Public test cases

Input

-1

Output

Input

20 -1

Output

Input

17 4 6 20 20 23 140 28 255 999999972 1 2 -1

Output

Input

4 4 4 4 4 4 4 4 4 4 4 4 -1

Output

Information

Author: Professorat de P1
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++