diff --git a/res/values-es-rUS/strings.xml b/res/values-es-rUS/strings.xml
index 4f1b1ca..3c9a660 100644
--- a/res/values-es-rUS/strings.xml
+++ b/res/values-es-rUS/strings.xml
@@ -157,8 +157,6 @@
     <string name="listSeparatorOtherInformation" msgid="7844959649638482329">"Otra información"</string>
     <string name="listSeparatorOtherInformation_edit" msgid="1326921768011367750">"Otras opciones"</string>
     <string name="listSeparatorMore_edit" msgid="858454837482243176">"Más"</string>
-    <string name="listTotalPhoneContacts" msgid="7371957507364352596">"<xliff:g id="NUM">%s</xliff:g> contactos con números de teléfono"</string>
-    <string name="listTotalAllContacts" msgid="4516547509985949443">"<xliff:g id="NUM">%s</xliff:g> contactos"</string>
     <string name="socialStreamIconLabel" msgid="4367712449555075376">"Social"</string>
     <string name="contactsIconLabel" msgid="7666609097606552806">"Contactos"</string>
     <string name="contactsFavoritesLabel" msgid="8417039765586853670">"Favoritos"</string>
diff --git a/res/values/strings.xml b/res/values/strings.xml
index 60f784d..e1cf4ca 100644
--- a/res/values/strings.xml
+++ b/res/values/strings.xml
@@ -427,10 +427,31 @@
     <string name="listSeparatorMore_edit">More</string>
 
     <!-- Displayed at the top of the contacts showing the total number of contacts visible when "Only contacts with phones" is selected -->
-    <string name="listTotalPhoneContacts"><xliff:g id="num">%s</xliff:g> contacts with phone numbers</string>
+    <plurals name="listTotalPhoneContacts">
+        <item quantity="one">Displaying 1 contact with phone number</item>
+        <item quantity="other">Displaying <xliff:g id="count">%d</xliff:g> contacts with phone numbers</item>
+    </plurals>
+
+    <!-- Displayed at the top of the contacts showing the zero as total number of contacts visible when "Only contacts with phones" is selected -->
+    <string name="listTotalPhoneContactsZero">No visible contacts with phone numbers</string>
 
     <!-- Displayed at the top of the contacts showing the total number of contacts visible when "Only contacts with phones" not selected -->
-    <string name="listTotalAllContacts"><xliff:g id="num">%s</xliff:g> contacts</string>
+    <plurals name="listTotalAllContacts">
+        <item quantity="one">Displaying 1 contact</item>
+        <item quantity="other">Displaying <xliff:g id="count">%d</xliff:g> contacts</item>
+    </plurals>
+
+    <!-- Displayed at the top of the contacts showing the zero total number of contacts visible when "Only contacts with phones" not selected -->
+    <string name="listTotalAllContactsZero">No visible contacts</string>
+
+    <!-- Displayed at the top of the contacts showing the total number of contacts found when "Only contacts with phones" not selected -->
+    <plurals name="listFoundAllContacts">
+        <item quantity="one">Found 1 contact</item>
+        <item quantity="other">Found <xliff:g id="count">%d</xliff:g> contacts</item>
+    </plurals>
+
+    <!-- Displayed at the top of the contacts showing the zero total number of contacts found when "Only contacts with phones" not selected -->
+    <string name="listFoundAllContactsZero">Contact not found</string>
 
     <!-- The description text for the social activity stream tab. Space is limited for this string, so the shorter the better -->
     <string name="socialStreamIconLabel">Social</string>
diff --git a/src/com/android/contacts/ContactsListActivity.java b/src/com/android/contacts/ContactsListActivity.java
index a0dcd6f..3250c41 100644
--- a/src/com/android/contacts/ContactsListActivity.java
+++ b/src/com/android/contacts/ContactsListActivity.java
@@ -233,7 +233,7 @@
             56 | MODE_MASK_PICKER | MODE_MASK_NO_PRESENCE | MODE_MASK_NO_FILTER;
     static final int MODE_GROUP = 57 | MODE_MASK_SHOW_PHOTOS;
     /** Run a search query */
-    static final int MODE_QUERY = 60 | MODE_MASK_NO_FILTER;
+    static final int MODE_QUERY = 60 | MODE_MASK_NO_FILTER | MODE_MASK_SHOW_NUMBER_OF_CONTACTS;
     /** Run a search query in PICK mode, but that still launches to VIEW */
     static final int MODE_QUERY_PICK_TO_VIEW = 65 | MODE_MASK_NO_FILTER | MODE_MASK_PICKER;
 
@@ -2215,14 +2215,7 @@
 
             // handle the total contacts item
             if (position == 0 && (mMode & MODE_MASK_SHOW_NUMBER_OF_CONTACTS) != 0) {
-                final LayoutInflater inflater = getLayoutInflater();
-                TextView totalContacts = (TextView) inflater.inflate(R.layout.total_contacts,
-                        parent, false);
-                int stringId = mDisplayOnlyPhones ? R.string.listTotalPhoneContacts
-                        : R.string.listTotalAllContacts;
-
-                totalContacts.setText(getString(stringId, getRealCount()));
-                return totalContacts;
+                return getTotalContactCountView(parent);
             }
 
             if (isShowAllContactsItemPosition(position)) {
@@ -2267,6 +2260,40 @@
             return v;
         }
 
+        private View getTotalContactCountView(ViewGroup parent) {
+            final LayoutInflater inflater = getLayoutInflater();
+            TextView totalContacts = (TextView) inflater.inflate(R.layout.total_contacts,
+                    parent, false);
+
+            String text;
+            int count = getRealCount();
+
+            if (mMode == MODE_QUERY || !TextUtils.isEmpty(getListView().getTextFilter())) {
+                text = getQuantityText(count, R.string.listFoundAllContactsZero,
+                        R.plurals.listFoundAllContacts);
+            } else {
+                if (mDisplayOnlyPhones) {
+                    text = getQuantityText(count, R.string.listTotalPhoneContactsZero,
+                            R.plurals.listTotalPhoneContacts);
+                } else {
+                    text = getQuantityText(count, R.string.listTotalAllContactsZero,
+                            R.plurals.listTotalAllContacts);
+                }
+            }
+            totalContacts.setText(text);
+            return totalContacts;
+        }
+
+        // TODO: fix PluralRules to handle zero correctly and use Resources.getQuantityText directly
+        private String getQuantityText(int count, int zeroResourceId, int pluralResourceId) {
+            if (count == 0) {
+                return getString(zeroResourceId);
+            } else {
+                String format = getResources().getQuantityText(pluralResourceId, count).toString();
+                return String.format(format, count);
+            }
+        }
+
         private boolean isShowAllContactsItemPosition(int position) {
             return mMode == MODE_JOIN_CONTACT && mJoinModeShowAllContacts
                     && mSuggestionsCursorCount != 0 && position == mSuggestionsCursorCount + 2;