Discrete logarithm

Given positive integers b, a_1, a_2, ..., a_N. Required to calculate the value of floor(log_ba_1), …, floor(log_ba_N) where, floor(x) — the largest integer not exceeding x.

Input

The input file contains the number N b a_1 a_2 ... a_N one number per line.

Output

The output file should contain N integers - the result of calculation.

1 ≤ N ≤ 1000, 2 ≤ b ≤ 100, 1 ≤ a_i < 10^1000 (ie the number contain up to 1000 digits).

Examples