Mô tả bài toán

Cho một số nguyên dương N. Hãy in tất cả các ước dương của N theo thứ tự tăng dần, mỗi ước một dòng.

Ràng buộc

1 ≤ N ≤ $ 10^5 $

Đầu vào

Dòng duy nhất chứa số N.

Đầu ra

In tất cả các ước dương của N, mỗi số trên một dòng, theo thứ tự tăng dần.

Ví dụ

Input

6

Output

1
2
3
6

Input

7

Output

1
7

Input

4

Output

1
2
4

Mô tả bài toán

Một số được gọi là "binary decimal" nếu đó là một số nguyên dương và tất cả các chữ số trong biểu diễn dạng thập phân của nó chỉ là 0 hoặc 1. Ví dụ: 1010111 là một binary decimal, trong khi 10201 và 787788 thì không phải.

Cho một số nguyên n, hãy biểu diễn n dưới dạng tổng của một số (có thể lặp) các binary decimals. Hãy tính số lượng nhỏ nhất các binary decimals cần để biểu diễn n.

Ràng buộc

Số lượng test t: 1 ≤ t ≤ 1000

Với mỗi test, 1 ≤ n ≤ 10^9

Đầu vào

Dòng đầu chứa một số nguyên t — số lượng test. Mỗi test gồm một dòng chứa một số nguyên n.

Đầu ra

Với mỗi test, in ra một dòng chứa một số nguyên — số lượng nhỏ nhất các binary decimals cần để biểu diễn n.

Ví dụ

Input

3
121
5
1000000000

Output

2
5
1

Ghi chú

Trong test 1: 121 có thể được biểu diễn như 110 + 11 hoặc 111 + 10.

Trong test 2: 5 = 1 + 1 + 1 + 1 + 1.

Trong test 3: 1000000000 tự thân là một binary decimal nên đáp án là 1.

Mô tả bài toán

Farmer John có ba xô đựng sữa lấy từ ba con bò Bessie, Elsie và Mildred. Mỗi xô có dung tích khác nhau và ban đầu chứa một lượng sữa nhất định (có thể không đầy).

Ông thực hiện tuần tự các lần rót sau đây: rót xô 1 vào xô 2, rồi xô 2 vào xô 3, rồi xô 3 vào xô 1, rồi lại xô 1 vào xô 2, ... theo vòng lặp như vậy, tổng cộng 100 lần rót. Khi rót xô a vào xô b, ông sẽ rót hết mức có thể cho tới khi xô a rỗng hoặc xô b đầy.

Hỏi sau 100 lần rót, mỗi xô sẽ chứa bao nhiêu sữa?

Input

Dòng thứ nhất: hai số nguyên c1 m1 — dung tích và lượng sữa ban đầu trong xô 1.
Dòng thứ hai: c2 m2 — tương tự cho xô 2.
Dòng thứ ba: c3 m3 — tương tự cho xô 3.

1 ≤ m_i ≤ c_i ≤ $ 10^9 $

Output

In ba dòng, mỗi dòng một số nguyên, là lượng sữa còn lại trong xô 1, xô 2, xô 3 sau 100 lần rót.

Ví dụ

Input

10 3
11 4
12 5

Output

0
10
2

Ghi chú ngắn

Trạng thái ban đầu: 3 4 5

1. Rót 1->2: 0 7 5
2. Rót 2->3: 0 0 12
3. Rót 3->1: 10 0 2
4. Rót 1->2: 0 10 2
5. Rót 2->3: 0 0 12 ... và các trạng thái này lặp lại cho tới khi thực hiện đủ 100 lần.

Mô tả bài toán

Quảng trường Theatre Square có dạng hình chữ nhật kích thước n × m mét. Cần lát nền quảng trường bằng các viên đá vuông kích thước a × a mét.

Hỏi cần tối thiểu bao nhiêu viên đá để lát kín quảng trường. Có thể phủ ngoài diện tích quảng trường (tức là viên đá được đặt vượt ra ngoài rìa), nhưng không được phá vỡ viên đá. Các cạnh của viên đá phải song song với các cạnh của quảng trường.

Đầu vào

Dòng đầu chứa ba số nguyên dương n, m và a (1 ≤ n, m, a ≤ 10^9).

Đầu ra

In ra một số nguyên — số viên đá cần thiết tối thiểu.

Ví dụ

Input

6 6 4

Output

4

Mô tả bài toán

Ann thường đi tàu điện ngầm. Một vé cho một lượt đi có giá a rubles. Ngoài ra, cô có thể mua một loại vé đặc biệt dùng cho m lượt (có thể mua nhiều lần), mỗi vé như vậy có giá b rubles. Ann cần đi n lượt. Hỏi cô cần chi ít nhất bao nhiêu rubles để thực hiện n lượt đi?

Đầu vào

Dòng duy nhất chứa bốn số nguyên dương n, m, a, b (1 ≤ n, m, a, b ≤ 1000) — số lượt cần đi, số lần đi của vé đặc biệt, giá một vé một lượt và giá một vé đặc biệt.

Đầu ra

In ra một số nguyên — số tiền tối thiểu (rubles) cần chi.

Ví dụ

Input

6 2 1 2

Output

6

Input

5 2 2 3

Output

8

Ghi chú

Trong ví dụ 1, một cách tối ưu là mua mỗi lần một vé một lượt (6 × 1 = 6). Cũng có cách tối ưu khác, ví dụ mua ba vé m lượt (3 × 2 = 6).