FindMaxLessSum#12381
Sign in

FindMaxLessSum

2 seconds
256 megabytes
Medium

You are given a positive integer .

Find the largest non-negative integer (0 \le v < n) such that the sum of the digits of is strictly less than the sum of the digits of .

The sum of digits is calculated in the decimal system (base ).

Input

The first line contains a single integer (1 \le t \le 10^5) — the number of test cases.

Each test case consists of a single line containing an integer (1 \le n \le 10^9).

Output

For each test case, output the largest integer that satisfies the conditions.

The number should be printed without any leading zeros.

Examples

Example 1

Loading
Loading

Scoring

  1. Subtask ( points): \sum n \le 10^6 over all test cases.

  2. Subtask ( points): No additional constraints.