Multiple of 3

3.2

36 votes
Greedy algorithm, Algorithms, Basics of Greedy Algorithms, Greedy Algorithms
Problem

You are given an integer N and your task is to make N a multiple of 3. In order to make N multiple of 3, you can insert at most one digit in N.

Your task is to find the minimum possible N which is a multiple of 3 after inserting at most one digit.

Note: You can insert the digit anywhere in N and also you need not necessarily insert.

Input format

  • The first line contains an integer T denoting the number of test cases.
  • The first line of each test case contains an integer N.

Output format

For each test case:

  • Print the minimum N which is a multiple of 3 after at most one insertion.

Constraints

  • 1T20000
  • 1N109
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Self explainatory

Editor Image

?