Balls

Time Limit: 3 sec

 

The Problem

Mac is an attentive student of class nine. He studied in a well known school of Chittagong. His  aim is to become a good programmer. But he knows a little about programming. To learn programming every week he attends in a programming class in OUTSBOOK. One day the trainer of the class gave him a problem to solve. Since he is beginner in programming so he is not able to solve this problem. He knows that you are a good programmer and a senior student of OUTSBOOK. So he needs your help. Now you have to help him. The problem is described below.

 

In a store house there are N boxes and each box having a serial number starting from 1 to N.

Here box 1 has 1 ball and box 2 has 2 balls.

And from box 3 to N there are

Balls in box P = balls of box (P/2) + balls of box (P/3)

 

Example

If P = 3

Balls in box 3rd = balls of box (3/2) + balls of box (3/3)

Balls in box 3rd = balls of box 1 + balls of box 1

Balls in box 3rd = 1 + 1

Balls in box 3rd = 2

 

Given an integer number N, Now your task is to tell Mac how many balls in box N.

 

The Input

The input is starts with T (T<=100), the number of test case. The next T lines will contain a

single positive integer N (1<= N <= 10^12), the serial number of the box.

 

The Output

For each line of input print the number of balls in box N in separate line.

 

Sample Input

3

1

3

5

 

Sample Output

1

2

3

 

 

 

[University Level]

Inter School & College Programming Contest (ISCPC) 2017

Problem Setter: Milton Deb